[费用流+拆点]hdoj 2686&&hdoj 3376：Matrix&&Matrix Again
大致题意：
? ? 给出一个n*n的矩阵，现在要从左上角走到右下角，规定除了（0，0）（n-1，n-1）之外不能走重复的路，求来回路径覆盖到的数字之和最大是多少，两题除了数据量之外的，其他完全一样。
?
大致思路：
? ? 把矩阵的每个元素拆点，用于限制每个点经过的次数，并且与其下面的点和右边的点相连。然后对左上角和右下角特殊处理……求出费用流即可。因为只要增广两次，所以3376的数据量并不需要担心
?
#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int inf=99999999;const int nMax=800000;const int mMax=4000000;struct{ int u,v, cap, cost, next, re;}edge[mMax];int ans,maxf;int k,edgeHead[nMax];int que[nMax],pre[nMax],dis[nMax];bool vis[nMax],flag;void addEdge(int u,int v,int ca,int co){////始点 终点 流量 花费// cout<<u<<" "<<v<<" "<<ca<<" "<<co<<endl; edge[k].v=v; edge[k].cap=ca; edge[k].cost=co; edge[k].next=edgeHead[u]; edge[k].re=k + 1; edgeHead[u]=k ++; edge[k].v=u; edge[k].cap=0; edge[k].cost=-co; edge[k].next=edgeHead[v]; edge[k].re=k - 1; edgeHead[v]=k ++;}bool spfa(int s,int t,int n){ //始点，终点，总点数 int i, head = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方 for(i = 0; i <= n; i ++){ dis[i] = -inf;//////////// vis[i] = false; } dis[s] = 0; que[0] = s; vis[s] = true; while(head != tail){ int u = que[head]; for(i = edgeHead[u]; i != 0; i = edge[i].next){ int v = edge[i].v; if(edge[i].cap && dis[v] <dis[u] + edge[i].cost){//////// dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]){ vis[v] = true; que[tail ++] = v; if(tail == nMax) tail = 0; } } } vis[u] = false; head++; if(head ==nMax) head = 0; } if(dis[t] ==-inf) return false;/////////// return true;}void end(int s,int t){ int u, p; for(u = t;u!=s;u=edge[edge[p].re].v){ p = pre[u]; edge[p].cap-=1; edge[edge[p].re].cap+=1; ans+=edge[p].cost; } maxf+=1; //总流量}int map[700][700];int main(){int n,i,j,s,t,a,b;while(scanf("%d",&n)!=EOF){ans=0;k=1;memset(edgeHead,0,sizeof(edgeHead));for(i=0;i<n;i++){for(j=0;j<n;j++){scanf("%d",&map[i][j]);}}for(i=0;i<n;i++){for(j=0;j<n;j++){a=i*n+j;b=a+n*n;addEdge(a,b,1,map[i][j]);if((i==0&&j==0)||(i==n-1&&j==n-1)){addEdge(a,b,1,map[i][j]);}if(j!=n-1){addEdge(b,a+1,inf,0);}if(i!=n-1){addEdge(b,a+n,inf,0);}}}//cout<<"fuck\n";s=0;t=n*n*2-1;while(spfa(s,t,n*n*2))end(s,t);cout<<ans-map[0][0]-map[n-1][n-1]<<endl;}return 0;}?