poj 1274 The Perfect Stal

二分匹配传送门[here]

原题传送门[here]

　　题意大概说一下，就是有N头牛和M个牛棚，每头牛愿意住在一些牛棚，求最大能够满足多少头牛的要求。

　　很明显就是一道裸裸的二分图最大匹配，但是为了练练网络流（做其它的题的时候，神奇地re掉了，于是就写基础题了）的最大流算法，就做做这道题。

　　每一个牛都可一看成是个源点，每一个牛棚都可以看成是个汇点，但是一个网络应该只有一个汇点和一个源点才对，于是构造一个连接每个牛的超级源点，一个连接每个牛棚的超级汇点，每条边的容量为1，然后最大流Dinic算法（其它最大流算法也行）就行了。

Code_{极其不简洁的代码}

 /**

  * poj.org

  * Problem#1274

  * Accepted

  * Time:16ms

  * Memory:1980k

  */

 #include<iostream>

 #include<sstream>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<cctype>

 #include<ctime>

 #include<queue>

 #include<set>

 #include<map>

 #include<stack>

 #include<vector>

 #include<algorithm>

 using namespace std;

 typedef bool boolean;

 #define smin(a, b) (a) = min((a), (b))

 #define smax(a, b) (a) = max((a), (b))

 #define INF 0xfffffff

 template<typename T>

 inline boolean readInteger(T& u){

     char x;

     int aFlag = ;

     while(!isdigit((x = getchar())) && x != '-' && ~x);

     if(!(~x))    return false;

     if(x == '-'){

         aFlag = -;

         x = getchar();

     }

     for(u = x - ''; isdigit((x = getchar())); u = u *  + x - '');

     ungetc(x, stdin);

     u *= aFlag;

     return true;

 }

 ///map template starts

 typedef class Edge{

     public:

         int end;

         int next;

         int cap;

         int flow;

         Edge(const int end = , const int next = , const int cap = , const int flow = ):end(end), next(next), cap(cap), flow(flow){}

 }Edge;

 typedef class MapManager{

     public:

         int ce;

         int *h;

         Edge *edge;

         MapManager(){}

         MapManager(int points, int limit):ce(){

             h = new int[(const int)(points + )];

             edge = new Edge[(const int)(limit + )];

             memset(h, , sizeof(int) * (points + ));

         }

         inline void addEdge(int from, int end, int cap, int flow){

             edge[++ce] = Edge(end, h[from], cap, flow);

             h[from] = ce;

         }

         inline void addDoubleEdge(int from, int end, int cap){

             addEdge(from, end, cap, );

             addEdge(end, from, cap, cap);

         }

         Edge& operator [](int pos){

             return edge[pos];

         }

         inline int reverse(int pos){        //反向边

             return (pos & ) ? (pos + ) : (pos - );

         }

         inline void clear(){

             delete[] edge;

             delete h;

             ce = ;

         }

 }MapManager;

 #define m_begin(g, i)     (g).h[(i)]

 #define m_end(g, i)     (g).edge[(i)].end

 #define m_next(g, i)     (g).edge[(i)].next

 #define m_cap(g, i)     (g).edge[(i)].cap

 #define m_flow(g, i)     (g).edge[(i)].flow

 ///map template ends

 int n, m;

 int t;

 MapManager g;

 inline boolean init(){

     if(!readInteger(n))    return false;

     readInteger(m);

     t = n + m + ;

     g = MapManager(t + , (n + ) * (m + ) * );

     for(int i = , a, b; i <= n; i++){

         readInteger(a);

         while(a--){

             readInteger(b);

             g.addDoubleEdge(i, b + n, );

         }

     }

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

         g.addDoubleEdge(, i, );

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

         g.addDoubleEdge(i + n, t, );

     return true;

 }

 boolean *visited;

 int* divs;

 queue<int> que;

 inline boolean getDivs(){

     memset(visited, false, sizeof(boolean) * (t + ));

     divs[] = ;

     visited[] = true;

     que.push();

     while(!que.empty()){

         int e = que.front();

         que.pop();

         for(int i = m_begin(g, e); i != ; i = g[i].next){

             int& eu = g[i].end;

             if(!visited[eu] && g[i].flow < g[i].cap){

                 divs[eu] = divs[e] + ;

                 visited[eu] = true;

                 que.push(eu);

             }

         }

     }

     return visited[t];

 }

 int blockedflow(int node, int minf){

     if(node == t || minf == )    return minf;

     int f, flow = ;

     for(int i = m_begin(g, node); i != ; i = m_next(g, i)){

         int& e = g[i].end;

         if(divs[e] == divs[node] +  && visited[e] && (f = blockedflow(e, min(minf, g[i].cap - g[i].flow))) > ){

             flow += f;

             g[i].flow += f;

             g[g.reverse(i)].flow -= f;

             minf -= f;

             if(minf == )    return flow;

         }

     }

     return flow;

 }

 inline int maxflow(){

     visited = new boolean[(const int)(t + )];

     divs = new int[(const int)(t + )];

     int res = ;

     while(getDivs()){

         res += blockedflow(, INF);

     }

     return res;

 }

 inline void solve(){

     int res = maxflow();

     cout << res << endl;

 }

 inline void clear(){

     delete[] visited;

     delete[] divs;

     g.clear();

 }

 int main(){

     while(init()){

         solve();

         clear();

     }

     return ;

 }

巴特西

poj 1274 The Perfect Stal - 网络流

Code_{极其不简洁的代码}

最新文章

热门文章

巴特西

poj 1274 The Perfect Stal - 网络流

Code极其不简洁的代码

最新文章

热门文章

Code_{极其不简洁的代码}