本文共 3604 字，大约阅读时间需要 12 分钟。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #define INF 0x3f3f3f3f 15 #define OPEN_FILE 16 #define MAXN 626 17 using namespace std; 18 19 int n; 20 int win[MAXN], remain[MAXN][MAXN]; 21 struct Edge{ 22 int from, to, cap, flow; 23 //Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){}; 24 }; 25 bool comp(const Edge& a, const Edge& b){ 26 return (a.from < b.from || (a.from == b.from && a.to < b.to)); 27 } 28 struct Dinic{ 29 int n, m, i, s, t; 30 Edge e; 31 vector edges; 32 vector G[MAXN]; 33 int d[MAXN], cur[MAXN]; 34 bool vis[MAXN]; 35 void init(int n){ 36 this->n = n; 37 for (i = 0; i <= n; i++){ 38 G[i].clear(); 39 } 40 edges.clear(); 41 } 42 void AddEdge(int from, int to, int cap){ 43 edges.push_back(Edge{ from, to, cap, 0 }); 44 edges.push_back(Edge{ to, from, 0, 0 }); 45 m = edges.size(); 46 G[from].push_back(m - 2); 47 G[to].push_back(m - 1); 48 } 49 bool BFS(){ 50 memset(vis, 0, sizeof(vis)); 51 queue Q; 52 Q.push(s); 53 d[s] = 0; 54 vis[s] = 1; 55 while (!Q.empty()){ 56 int x = Q.front(); 57 Q.pop(); 58 for (i = 0; i < G[x].size(); i++){ 59 Edge& e = edges[G[x][i]]; 60 if (!vis[e.to] && e.cap > e.flow){ 61 vis[e.to] = true; 62 d[e.to] = d[x] + 1; 63 Q.push(e.to); 64 } 65 } 66 } 67 return vis[t]; 68 } 69 int DFS(int x, int a){ 70 if (x == t || a == 0) return a; 71 int flow = 0, f; 72 for (int& i = cur[x]; i < G[x].size(); i++){ 73 Edge& e = edges[G[x][i]]; 74 if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0){ 75 e.flow += f; 76 edges[G[x][i] ^ 1].flow -= f; 77 flow += f; 78 a -= f; 79 if (a == 0) break; 80 } 81 } 82 return flow; 83 } 84 int MaxFlow(int s, int t, int need){ 85 int flow = 0; 86 this->s = s; 87 this->t = t; 88 while (BFS()){ 89 memset(cur, 0, sizeof(cur)); 90 flow += DFS(s, INF); 91 if (flow > need) return flow; 92 } 93 return flow; 94 } 95 bool checkFull(int s){ 96 for (int i = 0; i < G[s].size(); i++){ 97 if (edges[G[s][i]].flow != edges[G[s][i]].cap){ 98 return false; 99 }100 }101 return true;102 }103 };104 105 int main()106 {107 #ifdef OPEN_FILE108 freopen("in.txt", "r", stdin);109 freopen("out.txt", "w", stdout);110 #endif // OPEN_FILE111 int T, x;112 scanf("%d", &T);113 for (int cas = 1; cas <= T; cas++){114 scanf("%d", &n);115 memset(win, 0, sizeof(win));116 for (int i = 1; i <= n; i++){117 scanf("%d%d", &win[i], &x);118 }119 memset(remain, 0, sizeof(remain));120 int p = 0;121 for (int i = 1; i <= n; i++){122 for (int j = 1; j <= n; j++){123 scanf("%d", &x);124 if (i == j) continue;125 remain[i][0] += x;126 if (remain[i][j] == 0 && remain[j][i] == 0){127 remain[i][j] = x;128 ++p;129 }130 }131 }132 int s = 0, t = n + p + 1, q;133 bool flag, first;134 Dinic ex;135 first = false;136 for (int k = 1; k <= n; k++){137 ex.init(n * n);138 flag = false;139 q = 1;140 int total = win[k] + remain[k][0];141 for (int i = 1; i <= n; i++){142 for (int j = i + 1; j <= n; j++){143 if (!remain[i][j]) continue;144 ex.AddEdge(s, q, remain[i][j]);145 ex.AddEdge(q, p + i, INF);146 ex.AddEdge(q, p + j, INF);147 q++;148 }149 if (total - win[i] < 0) {150 flag = true;151 break;152 }153 ex.AddEdge(p + i, t, total - win[i]);154 }155 if (flag){156 continue;157 }158 ex.MaxFlow(s, t, INF);159 if (ex.checkFull(0)){160 if (first){161 printf(" ");162 }163 printf("%d", k);164 first = true;165 }166 }167 printf("\n");168 }169 }
转载于:https://www.cnblogs.com/macinchang/p/4491921.html