2018沈阳网赛F--上下界网络流

建图：

首先加一个源点s和汇点t，分别连接在二分图的左边和右边，每条弧的上下界为【L, R】，二分图左边和右边之间连弧上下界为【0，1】，其实就相当于连弧为1。

然后问题就转换为：有源汇最大流。

继续建图：

建立弧<t,s><，容量下界为00，上界为∞∞。

加一个超级源ss和超级汇tt

对于所有有上下界的弧（也就是s，t分别连接左边和右边的弧）进行分边

一条为<ss,v>，容量为L；

一条为<u,tt>>，容量为L；

一条为<u,v>，容量为R-L。

其中前两条弧一般称为附加弧。

然后跑一遍最大流，如果ss所有的出边（或者是TT所有的入边）都满流，就输出Yes

以后再加图说明吧....

（代码说明一下.. 0为超级源，NV为超级汇， NV-2为源， NV-1为汇）

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <vector>

 #include <queue>

 using namespace std;

 const int N = ;

 const int inf = 0x3f3f3f;

 struct Edge

 {

     int from,to,cap,flow;

     Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f) {}

 };

 struct Din

 {

     int s,t;

     vector<Edge>edges;

     vector<int>G[N];

     bool vis[N];

     int d[N];

     int cur[N];

     void addedge(int from,int to,int cap)

     {

         edges.push_back(Edge(from,to,cap,));

         edges.push_back(Edge(to,from,,));

         int  m=edges.size();

         G[from].push_back(m-);

         G[to].push_back(m-);

     }

     bool bfs()

     {

         memset(vis,,sizeof(vis));

         queue<int>Q;

         Q.push(s);

         d[s]=;

         vis[s]=;

         while(!Q.empty())

         {

             int x=Q.front();

             Q.pop();

             for(int i=; i<G[x].size(); i++)

             {

                 Edge&e=edges[G[x][i]];

                 if(!vis[e.to]&&e.cap>e.flow)

                 {

                     vis[e.to]=;

                     d[e.to]=d[x]+;

                     Q.push(e.to);

                 }

             }

         }

         return vis[t];

     }

     int dfs(int x,int a)

     {

         if(x==t||a==)

             return a;

         int flow=,f;

         for(int i=cur[x]; i<G[x].size(); i++)

         {

             Edge&e=edges[G[x][i]];

             if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>)

             {

                 e.flow += f;

                 edges[G[x][i]^].flow -= f;

                 flow += f;

                 a -= f;

                 if(!a)

                     break;

             }

         }

         return flow;

     }

     int Maxflow(int s,int t)

     {

         this->s=s,this->t=t;

         int flow=;

         while(bfs())

         {

             memset(cur,,sizeof(cur));

             flow += dfs(s,inf);

         }

         return flow;

     }

 };

 int main()

 {

     int N,F,D;

     int cnt = ;

     while(scanf("%d%d%d",&N,&F,&D) != EOF)

     {

         Din tmp;

         int flag = ;

         int NV = N+F++, NE=;

         int a, b;

         int l, r;

         scanf("%d%d",&l, &r);

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

         {

             scanf("%d%d",&a, &b);

             tmp.addedge(a,N+b, );

         }

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

         {

             tmp.addedge(NV-,i, r-l);

             tmp.addedge(,i, l);

             tmp.addedge(NV-,NV, l);

         }

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

         {

             tmp.addedge(N+i,NV-, r-l);

             tmp.addedge(,NV-, l);

             tmp.addedge(N+i,NV, l);

         }

         tmp.addedge(NV-,NV-, inf);

         int tt = tmp.Maxflow(NE,NV);

         for(int i=; i<tmp.G[].size(); i++)

         {

             Edge &e=tmp.edges[tmp.G[][i]];

             if(e.flow < l){

                 flag = ;

                 break;

             }

         }

         cnt++;

         if(flag)

             printf("Case %d: Yes\n", cnt);

         else

             printf("Case %d: No\n", cnt);

     }

 }

巴特西

2018沈阳网赛F--上下界网络流

最新文章

热门文章