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 100 101 102 103 104 105 106 107 108
|
#include<queue> using namespace std; const int M=500050,N=1005,INF=1<<25; int n,sum=0,st,ed,w[N][N],c[N]; int head[N*N],cnt=0,d[N*N],cur[N*N]; struct {int to,next,flow,cap;} 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; } int F(int x,int y){return (x-1)*n+y;} void add(int u,int v,int cap) { e[cnt].next=head[u]; head[u]=cnt; e[cnt].to=v; e[cnt++].cap=cap; } int bfs(int s,int t) { while (!Q.empty()) Q.pop(); for(int i=1;i<=n*n+n+2;i++) d[i]=0; d[s]=1,Q.push(s); while (!Q.empty()&&!d[t]) { int x=Q.front();Q.pop(); for(int i=head[x];~i;i=e[i].next) { int to=e[i].to; if (e[i].flow<e[i].cap&&!d[to]) { d[to]=d[x]+1; Q.push(to); } } } return d[t]; } int dfs(int x,int t,int flow) { if (!flow||x==t) return flow; int ret=0,new_flow; for(int &i=cur[x];~i&&flow;i=e[i].next) { int to=e[i].to; if (d[x]+1==d[to]) { new_flow=dfs(to,t,min(flow,e[i].cap-e[i].flow)); e[i].flow+=new_flow; e[i^1].flow-=new_flow; ret+=new_flow; flow-=new_flow; }
} return ret; } int Dinic(int s,int t) { int ret=0; while (bfs(s,t)) { for(int i=1;i<=n*n+n+2;i++) cur[i]=head[i]; ret+=dfs(s,t,INF); } return ret; } int main() { n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) sum+=w[i][j]=read(); for(int i=1;i<=n;i++) c[i]=read(); st=n*n+n+1,ed=st+1; for(int i=1;i<=n*n+n+2;i++) head[i]=-1; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { add(st,F(i,j),w[i][j]+w[j][i]); add(F(i,j),st,0); add(F(i,j),n*n+i,INF); add(n*n+i,F(i,j),0); add(F(i,j),n*n+j,INF); add(n*n+j,F(i,j),0); } for(int i=1;i<=n;i++) { add(st,F(i,i),w[i][i]); add(F(i,i),st,0); add(F(i,i),n*n+i,INF); add(n*n+i,F(i,i),0); } for(int i=1;i<=n;i++) { add(n*n+i,ed,c[i]); add(ed,n*n+i,0); } printf("%dn",sum-Dinic(st,ed)); return 0; }
|
近期评论