cqoi2015网络吞吐量（bzoj3931,洛谷3171）

题目分析

在这样一道很裸很裸的模板题上爆0简直了，我觉得我可以退役了......

主要是想复杂了，完全不相信会有这么裸的省选题啊.....题意已经很明显了，就是要跑2遍Dijkstra最短路然后用网络流，当然如果你一定要用SPFA也可以，如果正着跑的dis[s]值加上反着跑的dis[t]值再加上这条边的长度是最短路的话，这条路就在最短路里面，选择。尊重题目意思，我用了Dijkstra。另外，一定要开long long,不开long long见祖宗啊，inf一定要开大。

因为流量的限制是在点上的，所以我们要拆点，一个点拆成两个，从这个点流向拆后的另一个点的流量是点流量限制，发现最短路后，从后面（已经经过流量筛选的）点连一条流量无穷大的点流到前面（还没流量限制）的点就可以了。

代码

#include<iostream> #include<algorithm> #include<string> #include<vector> #include<cstdlib> #include<cstdio> #include<cstring> #include<queue> #include<map> #include<climits> using namespace std; int n,m,sum=1,s,t; long long ma[505][505],dis[2][505],flow; long long fll[300005]; int h[1010],level[1010],que[1010],go[300008],ne[300008]; bool vis[505]; long long inf=99999999999;//一定要开大～大～大～ void add(int x,int y,long long z){ sum++;go[sum]=y;ne[sum]=h[x];h[x]=sum;fll[sum]=z; sum++;go[sum]=x;ne[sum]=h[y];h[y]=sum;fll[sum]=0;//反向边 } void dij(int bj,int ff){//最短路 int i,j,from=0; long long mi; dis[bj][ff]=0; for(i=1;i<=n-1;i++){ from=0;mi=inf; for(j=1;j<=n;j++) if(vis[j]==0&&mi>dis[bj][j]){ mi=dis[bj][j];from=j; } if(from==0)break; vis[from]=1; for(j=1;j<=n;j++) if(dis[bj][from]+ma[from][j]<dis[bj][j]) {dis[bj][j]=dis[bj][from]+ma[from][j];} } } long long dfs(int x,long long liu){//dinic算法 long long ans=0,kl; int i,j; if(x==t)return liu; for(i=h[x];i!=0;i=ne[i]) if(level[go[i]]==level[x]+1&&fll[i]>0){ kl=dfs(go[i],min(liu-ans,fll[i])); ans+=kl;fll[i]-=kl;fll[i^1]+=kl; if(ans==liu)return ans; } return ans; } bool bfs(){ int head=1,tail=1,i,from; for(i=1;i<=t;i++)level[i]=0; level[s]=1;que[1]=s; while(head<=tail){ from=que[head]; if(from==t)return 1; for(i=h[from];i!=0;i=ne[i]) if(level[go[i]]==0&&fll[i]>0){ level[go[i]]=level[from]+1; tail++;que[tail]=go[i]; } head++; } return 0; } long long find(){ long long ans=0; while(bfs())ans+=dfs(s,inf); return ans; } int main() { int i,j,x,y; long long z; memset(ma,0x3f,sizeof(ma)); scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ scanf("%d%d%lld",&x,&y,&z); ma[x][y]=min(ma[x][y],z);ma[y][x]=min(ma[y][x],z); } memset(dis,0x3f,sizeof(dis)); dij(1,1);memset(vis,0,sizeof(vis));dij(0,n); for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(ma[i][j]<inf&&dis[1][i]+dis[0][j]+ma[i][j]==dis[1][n]){//判断是不是最短路 add(i+n,j,inf);add(j+n,i,inf);//处理点流量限制的方法：i连到i+n号点上的流量是其流量 } } for(i=1;i<=n;i++){ scanf("%lld",&flow);if(i==1||i==n)continue; add(i,i+n,flow);} add(1,1+n,inf);add(n,n+n,inf); s=1;t=n+n; printf("%lld",find()); return 0; }