【题目大意】
N个盒子围成一圈。第i个盒子初始时有Ai个小球（∑Ai <= N）。每次可以把一个小球从一个盒子移到相邻的两个盒子之一。问最少需要移动多少次，使得每个盒子中小球的个数不超过1。（1 <= N <= 1000）
【建模方法】
一个比较直观的想法是每个盒子i作为一个点。若Ai > 1则连边(s, i, Ai-1, 0)；若Ai = 0则连边(i, t, 1, 0)。对任意两个盒子i, j，若Ai > 1并且Aj = 0，连边(i, j, ∞, min(|i - j|, n - |i - j|))。求一次最小费用流即为结果。但是这样构图复杂度会很高，边数会达到O(N^2)，不够聪明。更加简洁的方法是直接由每个盒子向与其相邻的两个盒子连边(i, j, ∞, 1)，总共也才2N条，将边数降到了O(N)，由TLE变成AC。
以上摘自Edelwiss《网络流建模汇总》
其实一开始基本上不会往那个T的方向去想。总之还是每种方案会对应一条边。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <queue> 5 #define maxn 5010 6 #define maxm 100010 7 #define INF 1<<30 8 using namespace std; 9 struct MCMF{ 10 int src,sink,e,n; 11 int first[maxn]; 12 int cap[maxm],cost[maxm],v[maxm],next[maxm]; 13 bool flag; 14 void init(){ 15 e = 0; 16 memset(first,-1,sizeof(first)); 17 } 18 19 void add_edge(int a,int b,int cc,int ww){ 20 //printf("add:%d to %d,cap = %d,cost = %d ",a,b,cc,ww); 21 cap[e] = cc;cost[e] = ww;v[e] = b; 22 next[e] = first[a];first[a] = e++; 23 cap[e] = 0;cost[e] = -ww;v[e] = a; 24 next[e] = first[b];first[b] = e++; 25 } 26 27 int d[maxn],pre[maxn],pos[maxn]; 28 bool vis[maxn]; 29 30 bool spfa(int s,int t){ 31 memset(pre,-1,sizeof(pre)); 32 memset(vis,0,sizeof(vis)); 33 queue<int> Q; 34 for(int i = 0;i <= n;i++) d[i] = INF; 35 Q.push(s);pre[s] = s;d[s] = 0;vis[s] = 1; 36 while(!Q.empty()){ 37 int u = Q.front();Q.pop(); 38 vis[u] = 0; 39 for(int i = first[u];i != -1;i = next[i]){ 40 if(cap[i] > 0 && d[u] + cost[i] < d[v[i]]){ 41 d[v[i]] = d[u] + cost[i]; 42 pre[v[i]] = u;pos[v[i]] = i; 43 if(!vis[v[i]]) vis[v[i]] = 1,Q.push(v[i]); 44 } 45 } 46 } 47 return pre[t] != -1; 48 } 49 50 int Mincost; 51 int Maxflow; 52 53 int MinCostFlow(int s,int t,int nn){ 54 Mincost = 0,Maxflow = 0,n = nn; 55 while(spfa(s,t)){ 56 int min_f = INF; 57 for(int i = t;i != s;i = pre[i]) 58 if(cap[pos[i]] < min_f) min_f = cap[pos[i]]; 59 Mincost += d[t] * min_f; 60 Maxflow += min_f; 61 for(int i = t;i != s;i = pre[i]){ 62 cap[pos[i]] -= min_f; 63 cap[pos[i]^1] += min_f; 64 } 65 } 66 return Mincost; 67 } 68 }; 69 MCMF g; 70 int N,K; 71 int id(int a,int b){ 72 return (a-1)*N + b; 73 } 74 int main(){ 75 while(scanf("%d%d",&N,&K) == 2){ 76 g.init(); 77 int nt = N*N; 78 for(int i = 1;i <= N;i++) 79 for(int j = 1;j <= N;j++){ 80 int a; 81 scanf("%d",&a); 82 g.add_edge(id(i,j),id(i,j)+nt,1,-a); 83 g.add_edge(id(i,j),id(i,j)+nt,K-1,0); 84 if(i < N) g.add_edge(id(i,j)+nt,id(i+1,j),K,0); 85 if(j < N) g.add_edge(id(i,j)+nt,id(i,j+1),K,0); 86 } 87 int src = 0,sink = nt*2+1; 88 g.add_edge(src,1,K,0); 89 g.add_edge(nt*2,sink,K,0); 90 printf("%d ",-g.MinCostFlow(src,sink,sink)); 91 } 92 return 0; 93 }