3931: [CQOI2015]网络吞吐量
题目：传送门
题解：
现在有点难受....跳了一个多钟...菜啊...
题意都把做法一起给了....最短路+网路流啊。
不想说话...记得开long long
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<queue> #define qread(x)x=read(); using namespace std; typedef long long LL; const LL INF=(1LL<<42); inline int read() { int f=1,x=0;char ch; while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } struct edge { int x,y,next;LL d; }e[222222];int last1[222222],len1; void ins1(int x,int y,LL d) { len1++; e[len1].x=x;e[len1].y=y;e[len1].d=d; e[len1].next=last1[x];last1[x]=len1; } struct node { int x,y,next,other;LL d; }a[222222];int last[222222],len; void ins(int x,int y,LL d) { int k1,k2; len++;k1=len; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; len++;k2=len; a[len].x=y;a[len].y=x;a[len].d=0; a[len].next=last[y];last[y]=len; a[k1].other=k2; a[k2].other=k1; } int n,m; int st,ed,head,tail; int list[222222],h[222222]; bool bt_h() { memset(h,0,sizeof(h));h[st]=1; list[1]=st;head=1;tail=2; while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(h[y]==0 && a[k].d>0) { h[y]=h[x]+1; list[tail++]=y; } } head++; } if(h[ed]>0)return true; return false; } LL find_flow(int x,LL flow) { if(x==ed)return flow; LL s=0,t; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(h[y]==(h[x]+1) && a[k].d>0 && flow>s) { t=find_flow(y,min(a[k].d,flow-s)); s+=t; a[k].d-=t;a[a[k].other].d+=t; } } if(s==0)h[x]=0; return s; } LL dd[222222]; bool v[222222]; void spfa() { for(int i=0;i<=n;i++)dd[i]=INF; memset(v,true,sizeof(v)); memset(list,0,sizeof(list)); list[1]=st;dd[st]=0;head=1;tail=2; while(head!=tail) { int x=list[head]; for(int k=last1[x];k;k=e[k].next) { int y=e[k].y; if(dd[y]>dd[x]+e[k].d) { //printf("%d %d ",x,y); dd[y]=dd[x]+e[k].d; if(v[y]==true) { v[y]=false; list[tail]=y;tail++;if(tail==n+1)tail=1; } } } list[head]=0; head++;if(head==n+1)head=1; v[x]=true; } } int main() { //freopen("network.in","r",stdin); //freopen("network.out","w",stdout); qread(n);qread(m); len1=0;memset(last1,0,sizeof(last)); len=0;memset(last,0,sizeof(last)); memset(list,0,sizeof(list)); st=1;ed=n*2; for(int i=1;i<=m;i++) { int x,y;LL d; qread(x);qread(y);scanf("%lld",&d); ins1(x,y,d); ins1(y,x,d); //printf("%d %d %lld ",x,y,d); } spfa(); memset(list,0,sizeof(list)); for(int i=1;i<=n;i++) { LL x;scanf("%lld",&x); if(i!=1 && i!=n) { ins(i,i+n,x); //printf("%d %d ",i,i+n); } } ins(st,1+n,INF); ins(n,ed,INF); for(int i=1;i<=n;i++) { for(int k=last1[i];k;k=e[k].next) { int y=e[k].y; if(dd[i]+e[k].d==dd[y]) { ins(i+n,y,INF); } } } LL ans=0; while(bt_h()) ans+=find_flow(st,INF); printf("%lld ",ans); return 0; }