首页 > 代码库 > URAL 1736 Chinese Hockey 网络流+建图
URAL 1736 Chinese Hockey 网络流+建图
题目链接:点击打开链接
题意:
给定n个队伍的得分情况,输出任意一个可行解。
n个队伍任意2个队伍 a, b 间有且仅有一场比赛。
比赛结果分4种:
1、a +3, b +0
2、a +0, b +3
3、a +2, b +1
4、a +1, b +2
我们发现其实每种结果2个队伍得分和总是3 且4种情况就是3的所有拆分和的形式。
所以我们把任意两个队伍组合成一个点。
把n个点连向源点,流上限为该队伍的得分。
对于1,2两个队伍
1 -> 点(1,2) 连流上限为3的边
2 -> 点(1,2) 连流上限为3的边
点(1,2) 到汇点连流上限为3的边。
若满流则有解。
1,2两个队伍间的情况就看点(1,2)的流入情况。
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; typedef long long ll; const int inf = (int)(1e9); const int M = 200 + 2; const int E = M * M * 6 + M * 3; const int N = M * M + M + 5; struct Edge { int from, to, cap, nex; }; int head[N], egnum; Edge eg[E]; int a[M], n, st, ed; int id[M][M], rid[N], tot; int win[M][M]; void add(int u, int v, int cap, int rw = 0) { Edge E = {u, v, cap, head[u]}; eg[egnum] = E; head[u] = egnum++; Edge E2 = {v, u, rw, head[v]}; eg[egnum] = E2; head[v] = egnum++; } int sign[N]; bool bfs(int from, int to) { memset(sign, -1, sizeof sign); sign[from] = 0; queue<int> q; q.push(from); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = eg[i].nex) { int v = eg[i].to; if (sign[v] == -1 && eg[i].cap) { sign[v] = sign[u] + 1; q.push(v); if (sign[to] != -1) return true; } } } return false; } int Stack[N], top, cur[N]; int dicnic(int from, int to) { int ans = 0; while (bfs(from, to)) { memcpy(cur, head, sizeof head); int u = from; top = 0; while (true) { if (u == to) { int flow = inf, loc; for (int i = 0; i < top; ++i) if (flow > eg[Stack[i]].cap) { flow = eg[Stack[i]].cap; loc = i; } for (int i = 0; i < top; ++i) { eg[Stack[i]].cap -= flow; eg[Stack[i] ^ 1].cap += flow; } ans += flow; top = loc; u = eg[Stack[top]].from; } for (int i = cur[u]; i != -1; cur[u] = i = eg[i].nex) if (eg[i].cap && (sign[u] + 1 == sign[eg[i].to])) break; if (cur[u] != -1) { Stack[top++] = cur[u]; u = eg[cur[u]].to; } else { if (top == 0) break; sign[u] = -1; u = eg[Stack[--top]].from; } } } return ans; } void init() { memset(head, -1, sizeof head); egnum = 0; } void pu(int x) { if (x == 0) { putchar('<'); } else if (x == 1) { putchar('>'); } else if (x == 2) { putchar('>'); putchar('='); } else { putchar('<'); putchar('='); } } void work() { int sum = 0, u, v; for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); sum += a[i]; } tot = n; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { id[i][j] = ++tot; rid[tot] = j; } st = ++tot; ed = ++tot; init(); for (int i = 0; i < n; ++i) add(st, i, a[i]); for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { add(i, id[i][j], 3); add(j, id[i][j], 3); add(id[i][j], ed, 3); } int g = dicnic(st, ed); if (g != sum) { puts("INCORRECT"); } else { memset(win, -1, sizeof win); puts("CORRECT"); for (int i = 0; i < egnum; ++i) { if (eg[i].from < n && eg[i].to > n && eg[i].to < st) { u = eg[i].from; v = rid[eg[i].to]; if (u == v) continue; if (u > v) std::swap(u, v); if (win[u][v] == -1) { if (eg[i].cap == 0) { win[u][v] = 1; //1 = win, 0 = los, 2 = little win, 3 = little los } else if (eg[i].cap == 1) { win[u][v] = 2; } else if (eg[i].cap == 2) { win[u][v] = 3; } else { win[u][v] = 0; } } } } for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { printf("%d ", i + 1); pu(win[i][j]); printf(" %d\n", j + 1); } } } int main() { while (~scanf("%d", &n)) work(); return 0; }
URAL 1736 Chinese Hockey 网络流+建图
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。