poj 3422 Kaka's Matrix Travels 费用流

//poj 3422 //sep9 #include <iostream> #include <queue> using namespace std; const int maxN=10024; const int maxM=20024; struct Edge { int v,f,w,nxt; }e[4*maxM+10]; int g[maxN+10]; int nume,src,sink; queue<int> Q; bool inq[maxN+10]; int dist[maxN+10]; int prev[maxN+10],pree[maxN+10]; void addedge(int u,int v,int c,int w) { e[++nume].v=v;e[nume].f=c;e[nume].w=w;e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0;e[nume].w=-w;e[nume].nxt=g[v];g[v]=nume; } bool find_path() { while(!Q.empty()) Q.pop(); memset(dist,⑴,sizeof(dist)); memset(inq,false,sizeof(inq)); Q.push(src); inq[src]=true; dist[src]=0; while(!Q.empty()){ int u=Q.front();Q.pop(); inq[u]=false; for(int i=g[u];i;i=e[i].nxt){ if(e[i].f>0&&dist[u]+e[i].w>dist[e[i].v]){ dist[e[i].v]=dist[u]+e[i].w; prev[e[i].v]=u; pree[e[i].v]=i; if(!inq[e[i].v]){ Q.push(e[i].v); inq[e[i].v]=true; } } } } return dist[sink]==⑴?false:true; } int max_cost_flow(int f) { int res=0; while(f>0){ if(find_path()==false) return ⑴; int d=f; for(int v=sink;v!=src;v=prev[v]) d=min(d,e[pree[v]].f); f-=d; res+=d*dist[sink]; for(int v=sink;v!=src;v=prev[v]){ e[pree[v]].f-=d; e[pree[v]^1].f+=d; } } return res; } void init() { memset(g,0,sizeof(g)); nume=1; } int main() { init(); int i,j,n,k; scanf("%d%d",&n,&k); src=2*n*n,sink=src+1; for(i=0;i<n;++i) for(j=0;j<n;++j){ int x; scanf("%d",&x); int u=i*n+j; int v=u+n*n; addedge(u,v,1,x); addedge(u,v,INT_MAX,0); if(i>0){ int t=(i⑴)*n+j+n*n; addedge(t,u,INT_MAX,0); } if(j>0){ int t=i*n+(j⑴)+n*n; addedge(t,u,INT_MAX,0); } } addedge(src,0,k,0); addedge(2*n*n⑴,sink,k,0); printf("%d",max_cost_flow(k)); return 0; }