CodeForces

题目链接https://codeforces.com/problemset/problem/546/E

最大流最难的就是建图了感觉，还有得看出这能是个最大流。当然这题还得输出过程我******

题目大意：告诉你哪些点是连着的并告诉你这个点一开时有多少人，然后每人可以都可以不动或者走到相邻的点，

给出末状态问你是否可能达到，如果可以类似要输出路径。

题目思路：这题建图感觉还行，源点到各个点的值为初始，各个点（另开一组对应本来1-4 对应5-8）到汇点的值为末状态，别忘连本点即1-5，2-6。

也就是求最大流是否和末状态加起来相同。找路径正向边因为在找增广路在减也就是要找反向边的值就行了。

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 typedef long long ll;
  5 const int maxn = 1e5 + 10;
  6 const int inf = 0x3f3f3f3f;
  7 int dir[10][10] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  8 
  9 int head[maxn], depth[maxn], cur[maxn], f[1010][1010];
 10 int cnt=1, x, y, ta, tb, ans, s, t, id, n, m,
 11 
 12 struct st
 13 {
 14     int to, next, w;
 15 }e[maxn];
 16 
 17 void add(int u, int v, int w) // cnt从2开始，从1开始错了也不知道被卡了哪里
 18 {
 19     e[++cnt].to = v;
 20     e[cnt].next = head[u];
 21     e[cnt].w = w;
 22     head[u] = cnt;
 23 }
 24 
 25 int bfs()
 26 {
 27     queue<int> q;
 28     memset(depth,0,sizeof(depth));
 29     depth[s] = 1;
 30     q.push(s);
 31     while(!q.empty())
 32     {
 33         int x = q.front(); q.pop();
 34         
 35         for(int i = head[x]; i; i = e[i].next)
 36         {
 37             int v = e[i].to;
 38             if(depth[v] == 0 && e[i].w > 0)
 39             {
 40                 depth[v] = depth[x] + 1;
 41                 q.push(v);
 42             }
 43             
 44         }
 45         
 46     }
 47     
 48     if(depth[t] > 0) return 1;
 49     else return 0;
 50 }
 51 
 52 int dfs(int u, int flow) // 内含多路增广优化
 53 {
 54     if(u == t) return flow;
 55     int ret = 0;
 56     
 57     for(int i = head[u]; i; i = e[i].next)
 58     {
 59         int v = e[i].to;
 60         if(depth[v] == depth[u] + 1 && e[i].w)
 61         {
 62             int id = dfs(v, min(e[i].w, flow - ret));
 63             ret += id; e[i].w -= id; e[i ^ 1].w += id;
 64             if(flow - ret == 0) break;
 65         }
 66         
 67     }
 68     
 69     if(!ret) depth[u] = -1; // 炸点优化
 70     return ret;
 71 }
 72 
 73 int dinic()
 74 {
 75     int ans = 0;
 76     while(bfs())
 77     {
 78         ans += dfs(s, inf);
 79     }
 80     return ans;
 81 }
 82 
 83 int main()
 84 {
 85     std::ios::sync_with_stdio(false);std::cin.tie(0);
 86     cin>>n>>m;
 87     s = 0; t = 2 * n + 1;
 88     for(int i = 1; i <= n; ++i)
 89     {
 90         cin>>x;
 91         add(s, i, x); add(i, s, 0); ta += x; 
 92     }
 93     
 94     for(int i = 1; i <= n; ++i)
 95     {
 96         cin>>x;
 97         add(i + n, t, x); add(t, i + n, 0); tb += x;
 98     }
 99     
100     for(int i = 1; i <= n; ++i)
101     {
102         add(i, i + n, inf); add(i + n, i, 0);
103     }
104     
105     for(int i = 1; i <= m; ++i)
106     {
107         cin>>x>>y;
108         add(x, y + n, inf); add(y + n, x, 0);
109         add(y, x + n, inf); add(x + n, y, 0);
110     }
111 
112     ans = dinic();
113     if(ans == tb && ta == tb)
114     {
115         cout<<"YES"<<endl;
116         for(int i = 1; i <= n; ++i)
117         {
118             for(int j = head[i]; j; j = e[j].next)
119             {
120                 int v = e[j].to;
121                 if(v > n) f[i][v - n] = e[j ^ 1].w;
122             }
123         }
124         
125         for(int i = 1; i <= n; ++i)
126         {
127             for(int j = 1; j <= n; ++j)
128             {
129                 cout<<f[i][j]<<' ';
130             }
131             cout<<endl;
132         }
133     }
134     
135     else cout<<"NO"<<endl;
136     
137     return 0;
138 }

这题只用了dinic的两个优化，还有个弧优化在其他篇里有。