285484026

「网络流 24 题」搭配飞行员
「网络流 24 题」搭配飞行员题解:很明显的二分图,先建立一个源点和一个汇点,从源点向每一个正驾驶员建一条容量为1...
扫描右侧二维码阅读全文
05
2018/10

「网络流 24 题」搭配飞行员

「网络流 24 题」搭配飞行员
题解:
很明显的二分图,先建立一个源点和一个汇点,从源点向每一个正驾驶员建一条容量为1的边,从每个副驾驶员向汇点建一条容量为1的边,从每个正驾驶员向他的搭档建容量为1的边,然后跑一边最大流
代码

#include <bits/stdc++.h>
#define pb push_back

const int MAXN = 1000000,INF = 1000000;

using namespace std;

int n,m,e = 2;
int head[MAXN],d[MAXN],cur[MAXN];

vector<int>a,b;

struct node{
   int v,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int c,int f){
   edge[e] = (node){v,c,f,head[u]};head[u] = e++;
   edge[e] = (node){u,0,f,head[v]};head[v] = e++;
}

inline void init()
{
   scanf("%d%d",&n,&m);
   int u,v;
   while(~scanf("%d%d",&u,&v)){
       if(u > v) swap(u,v);
       addedge(u,v,1,0);
       a.pb(u);b.pb(v);
   }
   
   for(int i = 1;i <= m;i++) addedge(0,i,1,0);
   for(int i = m+1;i <= n;i++) addedge(i,n+1,1,0);    
}

queue<int>Q;

inline bool bfs(int s){
   while(!Q.empty()) Q.pop();int x;
   Q.push(s);d[s] = 1;memset(d,0,sizeof(d));
   
   while(!Q.empty()){
       x = Q.front();Q.pop();
       for(int i = head[x];i;i = edge[i].next){
           int v = edge[i].v;
           if(edge[i].c > edge[i].f && !d[v]){
               d[v] = d[x] + 1;
               Q.push(v);
           } 
       } 
   }
   return d[n+1] ? true : false;
}

int dfs(int x,int a){
   if(x == n + 1 || a == 0) return a;
   int flow = 0,f;
   for(int & i = cur[x];i;i = edge[i].next){
       int v = edge[i].v,c = edge[i].c,f = edge[i].f;
       if(d[v] == d[x] + 1 && (f = dfs(v,min(a,c-f)) > 0)){
           edge[i].f += f;
           edge[i^1].f -= f;
           flow += f;
           a -= f;
           if(a == 0) break;
       } 
   }
   return flow;
}

inline int dinic(int s,int t)
{
   int flow = 0;
   while(bfs(s))
   {
       for(int i = s;i <= t;i++) cur[i] = head[i];
       flow += dfs(s,INF);
   }
   return flow;
}

int main()
{
   init();
   printf("%d",dinic(0,n+1));
   return 0;
}
Last modification:October 5th, 2018 at 01:45 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment