URAL - 1736 - Chinese Hockey

題意：n支隊伍打比賽，每2隊只進行1場比賽，規定時間內勝得3分，敗得0分，若是打到了加時賽，那麼勝得2分，敗得1分，給出n支隊伍最後的總得分，問這個結果是否是可能的，是的話輸出“CORRECT”及各場比賽各隊伍的比分情況，否則輸出"INCORRECT"(2 <= n <= 200)。   ——>>賽後師弟說這是一道網絡流大水題，果如其言～   設一個超級源點s，一個超級匯點t，各支隊伍各為1個結點，各場比賽也各為1個結點，從s到各場比賽各連1條邊，容量為3，從各場比賽到這場比賽的2支參賽隊伍各連1條邊，容量為3，最後從各支隊伍向t各連1條邊，容量為輸入的對應得分。然後，跑一次最大流，若最大流為滿流3 * n * (n-1) / 2，則得分是正確的，再根據各場比賽的流量輸出相應的數據，否則得分是不正確的。          

#include <cstdio>  
#include <cstring>  
#include <vector>  
#include <queue>  
  
using namespace std;  
  
const int maxv = 200 + 10;  
const int maxn = 40000 + 10;  
const int INF = 0x3f3f3f3f;  
  
int a[maxv], vs[maxv][maxv];  
  
struct Edge{  
    int u;  
    int v;  
    int cap;  
    int flow;  
};  
  
struct Dinic{  
    int n, m, s, t;  
    vector<Edge> edges;  
    vector<int> G[maxn];  
    bool vis[maxn];  
    int d[maxn];  
    int cur[maxn];  
  
    int addEdge(int uu, int vv, int cap){  
        edges.push_back((Edge){uu, vv, cap, 0});  
        edges.push_back((Edge){vv, uu, 0, 0});  
        m = edges.size();  
        G[uu].push_back(m-2);  
        G[vv].push_back(m-1);  
        return m-2;  
    }  
  
    bool bfs(){  
        memset(vis, 0, sizeof(vis));  
        queue<int> qu;  
        qu.push(s);  
        d[s] = 0;  
        vis[s] = 1;  
        while(!qu.empty()){  
            int x = qu.front(); qu.pop();  
            int si = G[x].size();  
            for(int i = 0; i < si; i++){  
                Edge& e = edges[G[x][i]];  
                if(!vis[e.v] && e.cap > e.flow){  
                    vis[e.v] = 1;  
                    d[e.v] = d[x] + 1;  
                    qu.push(e.v);  
                }  
            }  
        }  
        return vis[t];  
    }  
  
    int dfs(int x, int a){  
        if(x == t || a == 0) return a;  
        int flow = 0, f;  
        int si = G[x].size();  
        for(int& i = cur[x]; i < si; i++){  
            Edge& e = edges[G[x][i]];  
            if(d[x] + 1 == d[e.v] && (f = dfs(e.v, min(a, e.cap-e.flow))) > 0){  
                e.flow += f;  
                edges[G[x][i]^1].flow -= f;  
                flow += f;  
                a -= f;  
                if(a == 0) break;  
            }  
        }  
        return flow;  
    }  
  
    int Maxflow(int s, int t){  
        this->s = s;  
        this->t = t;  
        int flow = 0;  
        while(bfs()){  
            memset(cur, 0, sizeof(cur));  
            flow += dfs(s, INF);  
        }  
        return flow;  
    }  
};  
  
int main()  
{  
    int n;  
    while(scanf("%d", &n) == 1){  
        Dinic din;  
        int t = n + n * (n-1) / 2 + 1;  
        for(int i = 1; i <= n; i++){  
            scanf("%d", &a[i]);  
            din.addEdge(i, t, a[i]);  
        }  
        for(int i = 1, k = n+1; i <= n; i++)  
            for(int j = i+1; j <= n; j++, k++){  
                vs[i][j] = din.addEdge(0, k, 3);  
                din.addEdge(k, i, 3);  
                din.addEdge(k, j, 3);  
            }  
        if(din.Maxflow(0, t) == 3 * n * (n-1) / 2){  
            puts("CORRECT");  
            for(int i = 1; i <= n; i++)  
                for(int j = i+1; j <= n; j++){  
                    int L = din.edges[vs[i][j]+2].flow;  
                    int R = din.edges[vs[i][j]+4].flow;  
                    if(L == 3 && R == 0) printf("%d > %d\n", i, j);  
                    else if(L == 0 && R == 3) printf("%d < %d\n", i, j);  
                    else if(L == 2 && R == 1) printf("%d >= %d\n", i, j);  
                    else printf("%d <= %d\n", i, j);  
                }  
        }  
        else puts("INCORRECT");  
    }