题目：
做法就这样：
如果不是先连边再加边权(话说这样很奇怪啊)，而是算好边权再连边，再各种等价改一改，就能快2000ms，能在洛谷上A了...
代码如下：
#include#include #include #include 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 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\n",ans); return 0;}