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"); }
补充:软件开发 , C++ ,