cogs.12运输问题2题解

　　乍一看貌似和运输问题1没有任何区别，但本题有一个有意思的东西叫做下限，我个人称之为非强制下限，因为本题中要求的实际是我走这条边这条边才至少走下限的流，虽然出题人没说，但从样例来看确实是这样的，而强制下限目前还没做到，有待更新……

　　其实这道题还是板子，唯一与1不同的是它对建边提出了其他要求。即将边拆成三部分将原来u->v的流量设为上限-下限，s->v，u->t，流量为下限，详见刘汝佳《算法奥赛入门经典训练指南》（俗称蓝书）。至于s->v,u->t,直接统计一下，最后一起结算便是。

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 int n,zz=,a[];

 struct ro{

     int to;

     int next;

     int l;

     int from;

 }road[];

 void build(int x,int y,int z){

     zz++;

     road[zz].l=z;

     road[zz].from=x;

     road[zz].to=y;

     road[zz].next=a[x];

     a[x]=zz;

     zz++;

     road[zz].to=x;

     road[zz].from=y;

     road[zz].next=a[y];

     a[y]=zz;

 }

 int ss,tt;

 int pre[],flow[];

 queue<int> q1;

 int bfs(int s,int t){

     memset(pre,-,sizeof(pre));

     memset(flow,0x7f,sizeof(flow));

     int tt=flow[];

     pre[s]=;

     q1.push(s);

     while(!q1.empty())

     {

         int x=q1.front();q1.pop();

         for(int i=a[x];i>;i=road[i].next)

         {

             int y=road[i].to;

             if(pre[y]!=-||road[i].l<=)continue;

             pre[y]=i;

             flow[y]=min(flow[x],road[i].l);

             q1.push(y);

         }

     }

     if(flow[t]==tt)return -;

     else return flow[t];

 }

 int sum;

 int work(int s,int t){

     int ans=;

     while()

     {

         int x=bfs(s,t);

         if(x==-)break;

         ans+=x;

         int now=pre[t];

         while(now)

         {

             road[now].l-=x;

             road[now^].l+=x;

             now=pre[road[now].from];

         }

     }

     return ans;

 }

 int s[];

 int main(){

     freopen("maxflowb.in","r",stdin);

     freopen("maxflowb.out","w",stdout);

     scanf("%d",&n);

     tt=n+;

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=n;j++)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             if(!y) continue;

             s[i]-=x;

             s[j]+=x;

             build(i,j,y-x);

         }

     }

     build(n,,0x7fffffff);

     for(int i=;i<=n;i++)

     {

         if(s[i]>)

         {

             build(ss,i,s[i]);

         }

         else if(s[i]<)

         {

             build(i,tt,-s[i]);

         }

     }

     int an=work(ss,tt);

     int anss=work(,n);

     printf("%d\n",anss);

     //while(1);

     return ;

 }

代码挺丑，请谅解。

巴特西

cogs.12运输问题2题解

最新文章

热门文章