题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2039
https://www.luogu.org/problemnew/show/P1791
做法就这样：https://www.cnblogs.com/BearChild/p/6426850.html
如果不是先连边再加边权(话说这样很奇怪啊)，而是算好边权再连边，再各种等价改一改，就能快2000ms，能在洛谷上A了...
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; int const xn=1005,xm=5e6+5; int n,hd[xn],cur[xn],ct=1,to[xm],nxt[xm],dis[xn],S,T; ll c[xm],inf=1e17; queue<int>q; ll rd() { ll ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } void ade(int x,int y,ll f){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=f;} void add(int x,int y,ll f){ade(x,y,f); ade(y,x,0);} bool bfs() { memset(dis,0,sizeof dis); dis[S]=1; q.push(S); while(q.size()) { int x=q.front(); q.pop(); for(int i=hd[x],u;i;i=nxt[i]) if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+1,q.push(u); } return dis[T]; } ll dfs(int x,ll fl) { if(x==T)return fl; ll ret=0; for(int &i=cur[x],u;i;i=nxt[i]) { if(dis[u=to[i]]!=dis[x]+1||!c[i])continue; ll tmp=dfs(u,min(fl-ret,c[i])); if(!tmp)dis[u]=0; c[i]-=tmp; c[i^1]+=tmp; ret+=tmp; if(ret==fl)break; } return ret; } int main() { n=rd(); ll x,ans=0; S=0; T=n+1; for(int i=1;i<=n;i++)x=rd(),add(S,i,x); for(int i=1;i<=n;i++) { ll sum=0; for(int j=1;j<=n;j++) { x=rd(); add(i,j,x<<1ll); sum+=x; } add(i,T,sum); ans+=sum; } while(bfs()) { memcpy(cur,hd,sizeof hd); ans-=dfs(S,inf); } printf("%lld ",ans); return 0; }