BZOJ1834：[ZJOI2010]网络扩容—

BZOJ1834：[ZJOI2010]网络扩容——题解

阅读量：7083 次

发布时间：2019-06-28

本文共 1504 字，大约阅读时间需要 5 分钟。

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。

大水题，按照题意建图就可以完成第一问，然后对着残余网络换终点为T，n到T连容量为k的边，其他的点的路径再连容量INF费用为w的边跑费用流即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;const int INF=1e9;const int N=1010,M=30010;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}inline int getc(){ char ch=0; while(!isdigit(ch))ch=getchar(); return ch^48;}struct node{ int nxt,to,w,b;}edge[M];int head[N],cnt=-1;inline void add(int u,int v,int w,int b){ edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].b=b; edge[cnt].nxt=head[u];head[u]=cnt; edge[++cnt].to=u;edge[cnt].w=0;edge[cnt].b=-b; edge[cnt].nxt=head[v];head[v]=cnt;}int dis[N];bool vis[N];inline bool spfa(int s,int t,int n){ deque
           
            q; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)dis[i]=INF; dis[t]=0;q.push_back(t);vis[t]=1; while(!q.empty()){ int u=q.front(); q.pop_front();vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; int b=edge[i].b; if(edge[i^1].w&&dis[v]>dis[u]-b){ dis[v]=dis[u]-b; if(!vis[v]){ vis[v]=1; if(!q.empty()&&dis[v]