这道题是上一题的数据加强版，dinic表示毫无压力；
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cstdlib> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 const int maxn=55010; 10 const int inf=1000000000; 11 const int s=0,t=55001; 12 struct node{ 13 int y,next,flow,re; 14 }e[maxn*10]; 15 int linkk[maxn*3],len=0,n,m,w[maxn],sum=0; 16 void print(int x){printf("%d ",x);} 17 void print(int x,int y){printf("%d %d ",x,y);} 18 void insert(int x,int y,int flow){ 19 e[++len].y=y;e[len].flow=flow; 20 e[len].next=linkk[x];linkk[x]=len;e[len].re=len+1; 21 e[++len].y=x;e[len].flow=0; 22 e[len].next=linkk[y];linkk[y]=len;e[len].re=len-1; 23 } 24 void init(){ 25 scanf("%d%d",&n,&m); 26 for(int i=1;i<=n;i++)scanf("%d",&w[i]); 27 int x,y,v; 28 for(int i=1;i<=m;i++){ 29 scanf("%d%d%d",&x,&y,&v);sum+=v; 30 insert(s,i,v);insert(i,m+x,inf);insert(i,m+y,inf); 31 } 32 for(int i=1;i<=n;i++)insert(m+i,t,w[i]); 33 } 34 int q[maxn],tail=0,level[maxn],head=0; 35 bool bfs(){ 36 memset(level,-1,sizeof(level)); 37 head=0;tail=0;level[s]=1;q[++tail]=s; 38 while(++head<=tail){ 39 int x=q[head]; 40 for(int i=linkk[x];i;i=e[i].next){ 41 if(level[e[i].y]==-1&&e[i].flow){ 42 q[++tail]=e[i].y; 43 level[e[i].y]=level[x]+1; 44 } 45 } 46 } 47 return level[t]>0; 48 } 49 int find(int x,int flow){ 50 if(x==t)return flow; 51 int maxflow=0,d=0; 52 for(int i=linkk[x];i&&maxflow<flow;i=e[i].next){ 53 if(level[e[i].y]==level[x]+1&&e[i].flow){ 54 if(d=find(e[i].y,min(flow-maxflow,e[i].flow))){ 55 maxflow+=d; 56 e[i].flow-=d; 57 e[e[i].re].flow+=d; 58 } 59 } 60 } 61 if(!maxflow)level[x]=-1; 62 return maxflow; 63 } 64 void work(){ 65 int d=0,ans=0; 66 while(bfs()) 67 while(d=find(s,inf)) 68 ans+=d; 69 cout<<sum-ans<<endl; 70 } 71 int main(){ 72 freopen("1.in","r",stdin); 73 freopen("1.out","w",stdout); 74 init(); 75 work(); 76 }