做题笔记因特网带宽 Internet Bandwidth UVA820

首先，从题面入手，这题很明显的是一个网络流裸题
当你高高兴兴地打了一遍从P3376来的代码后，等待你的是一个

WA！

为什么？
现在看原文，我们可以发现一个很容易搞错的点：每条边都是无向边！（作者WA了5次都是跪在这个上面），所以，我们只要在加边的时候注意残量网络的流量上限不是0，这题就非常容易了。
我使用了蓝书风格的Dinic，

AC代码如下：

  1 #include <cstdio>
  2 #include <cctype>
  3 #include <vector>
  4 #include <iostream>
  5 #include <cstring>
  6 #include <queue>
  7 #define MAXN 100+5
  8 #define INF 200512233
  9 using namespace std;
 10 
 11 struct edge {
 12     int from,to,flow,cap;
 13     edge(int u,int v,int f,int c): from(u),to(v),flow(f),cap(c){};
 14 };
 15 
 16 inline int read() {
 17     int a = 0,f = 1;
 18     char v = getchar();
 19     while(!isdigit(v)) {
 20         if (v == '-') {
 21             f = -1;
 22         } 
 23         v = getchar();
 24     }
 25     while (isdigit(v)) {
 26         a = a * 10 + v - 48;
 27         v = getchar();
 28     }
 29     return a * f;
 30 }
 31 
 32 vector <int> G[MAXN];
 33 vector <edge> edges;
 34 int d[MAXN],n,m,s,t,T;
 35 int cur[MAXN];
 36 bool vis[MAXN];
 37 
 38 void init (int n) {
 39     for (int i = 1;i <= n;i++) {
 40         G[i].clear();
 41     }
 42     edges.clear();
 43 } 
 44 
 45 void addedge(int from,int to,int cap) {
 46     edges.push_back(edge(from,to,0,cap));
 47     edges.push_back(edge(to,from,0,cap));//最重要的一行代码！！！！！
 48     int m = edges.size();
 49     G[from].push_back(m-2);
 50     G[to].push_back(m-1);
 51 }
 52 
 53 bool bfs() {
 54     memset(vis,0,sizeof(vis));
 55     queue <int> q;
 56     q.push(s);
 57     d[s] = 0;
 58     vis[s] = 1;
 59     while (!q.empty()) {
 60         int x = q.front();
 61         //printf("bfs: x:%d\n",x);
 62         q.pop();
 63         for (int i = 0;i < G[x].size();i++) {
 64             edge& e = edges[G[x][i]];
 65             if (!vis[e.to] && e.cap > e.flow) {//考虑残量网络中的 
 66                 vis[e.to] = 1;
 67                 d[e.to] = d[x] + 1;
 68                 q.push(e.to);
 69             }
 70         }
 71     }
 72     return vis[t];//返回是否有增广路 
 73 }
 74 
 75 int dfs(int x,int a) {
 76     //printf("dfs: x:%d a:%d\n",x,a);
 77     if (x == t || a == 0) {
 78         return a;
 79     }
 80     int flow = 0,f;
 81     for (int& i = cur[x];i < G[x].size();i++) {
 82         edge& e = edges[G[x][i]];
 83         if (d[x] + 1 == d[e.to] && (f = dfs(e.to,min(a,e.cap - e.flow)))) {
 84             e.flow += f;
 85             edges[G[x][i]^1].flow -= f;
 86             flow += f;
 87             a -= f;
 88             if (a == 0) {
 89                 break;
 90             }
 91         }
 92     }
 93     return flow;
 94 }
 95 
 96 int maxflow() {
 97     int flow = 0;
 98     while (bfs()) {
 99         memset(cur,0,sizeof(cur));
100         flow += dfs(s,INF);
101     }
102     return flow;
103 }
104 
105 int main() {
106     while(n = read()) {
107         init(n);
108         s = read(),t = read(),m = read();
109         for (int i = 1;i <= m;i++) {
110             int u = read(),v = read(),f = read();
111             addedge(u,v,f);
112         } 
113         int ans = maxflow();
114         printf("Network %d\n",++T);
115         printf("The bandwidth is %d.\n\n",ans);
116     }
117     return 0;
118 }

做题笔记 因特网带宽 Internet Bandwidth UVA820

WA！

做题笔记因特网带宽 Internet Bandwidth UVA820