Codeforces Round #277.5 Div. 2 D. Unbearable Controversy of Being

題目鏈接:http://codeforces.com/contest/489/problem/D

題意

給定一有向圖,求這樣的

子圖有多少個

解法

暴力枚舉
先統計出來cont[a][c]
cont[a][c]表示從a到c進過b這樣的路徑條數
最後O(n²)枚舉a和b,ans+=cont[a][c]*(cont[a][c]-1)/2

const int N=3005;
typedef long long LL;
vector<int> g[N];
LL cont[N][N];
void init() {
    memset(cont,0,sizeof(cont));
    for(int i=0;i<N;i++) g[i].clear();
}
void solve() {
    int n,m;
    while(cin>>n>>m) {
        int u,v;
        for(int i=0;i<m;i++) {
            cin>>u>>v; g[u].push_back(v);
        }
        for(int i=1;i<=n;i++) {
            for(int j=0;j<g[i].size();j++) {
                int u=g[i][j];
                for(int k=0;k<g[u].size();k++) {
                    int v=g[u][k];
                    if(i==u||u==v||i==v) continue;
                    cont[i][v]++;
                }
            }
        }
        LL res=0;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                res+=cont[i][j]*(cont[i][j]-1)/2;
            }
        }
        cout<<res<<endl;
        init();
    }
}