1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
|
#include<queue> using namespace std; const int N=505,M=100000,INF=1<<30; int n,st,ed,w[N][N],cost; int head[N],pre[N],c[N],cnt=0,d[N],inq[N]; struct {int to,next,cap,flow,cost;} e[M<<1]; queue<int> Q; inline int read() { register int x=0,t=1; register char ch=getchar(); while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if (ch=='-') t=-1,ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t; } void add(int u,int v,int cap,int cost) { e[cnt].next=head[u]; head[u]=cnt; e[cnt].to=v; e[cnt].cost=cost; e[cnt++].cap=cap; } int SPFA(int s,int t) { for(int i=1;i<=n*3+2;i++) d[i]=INF,c[i]=0; d[s]=0,c[s]=INF,Q.push(s); while (!Q.empty()) { int x=Q.front(); Q.pop(),inq[x]=0; for(int i=head[x];~i;i=e[i].next) { int to=e[i].to,cost=e[i].cost; if (e[i].flow<e[i].cap&&d[x]+cost<d[to]) { d[to]=d[x]+cost; c[to]=min(c[x],e[i].cap-e[i].flow); pre[to]=i; if (!inq[to]) Q.push(to),inq[to]=1; } } } return c[t]; } void update(int x,int to,int flow) { for(int i=x;i!=to;i=e[pre[i]^1].to) { e[pre[i]].flow+=flow; e[pre[i]^1].flow-=flow; } } int MCMF(int s,int t) { cost=0; int ret=0,new_flow; while (new_flow=SPFA(s,t)) { ret+=new_flow; cost+=new_flow*d[t]; update(t,s,new_flow); } return ret; } int main() { n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) w[i][j]=read(); st=n*3+1,ed=st+1; for(int i=1;i<=n*3+2;i++) head[i]=-1; for(int i=1;i<=n;i++) add(st,i,1,0),add(i,st,0,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { add(j,i+n,1,w[i][j]); add(i+n,j,0,-w[i][j]); } for(int i=n+1;i<=n*2;i++) add(i,i+n,1,0),add(i+n,i,0,0); for(int i=n*2+1;i<=n*3;i++) add(i,ed,INF,0),add(ed,i,0,0); MCMF(st,ed); printf("%dn",cost); for(int i=1;i<=n*3+2;i++) head[i]=-1; for(int i=1;i<=n;i++) add(st,i,1,0),add(i,st,0,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { add(j,i+n,1,-w[i][j]); add(i+n,j,0,w[i][j]); } for(int i=n+1;i<=n*2;i++) add(i,i+n,1,0),add(i+n,i,0,0); for(int i=n*2+1;i<=n*3;i++) add(i,ed,INF,0),add(ed,i,0,0); MCMF(st,ed); printf("%dn",-cost); return 0; }
|
近期评论