Luogu P1894 [USACO4.2]The Perfect Stall

传送门

是道绿题？？？二分图（网络流）不应该是蓝打底？？？

这题浏览一遍就知道是二分图（网络流）算法喽，二分图代码太短，不想写（←这人？？？），所以就拿网络流练练手。

设源点S=0，汇点T=n+m+1。

从S向每头牛建一条流量为1的边。

从每头牛向它们喜欢的牛栏建一条流量为1的边。

从牛栏向T建一条流量为1的边。

然后跑最大流就可以了。

CODE：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <cctype>

 #include <queue>

 #include <cmath>

 #include <set>

 #include <stack>

 #include <utility>

 #include <map>

 #include <string>

 #include <vector>

 #include <list>

 #include <deque>

 #include <iterator>

 #include <iomanip>

 #include <future>

 #include <ctime>

 #define zxy(i,a,b) for(int i = a ; i <= b ; i++)

 #define zxyzxy(i,a,b) for(int i = a ; i < b ; i++)

 #define yxz(i,a,b) for(int i = a ; i >= b ; i--)

 #define yxzyxz(i,a,b) for(int i = a ; i > b ; i--)

 #define gameover printf("\n")

 #define N 1000005

 #define mod 100003

 #define INF 0x7fffffff

 #define PI 3.14159265358979323846

 #define y1 y111111111111

 #define bin return

 #define mt(a,val) memset(a,val,sizeof(a))

 #define M 20

 typedef long long ll;

 typedef double db;

 typedef float fl;

 typedef char cr;

 using namespace std;

 int read()

 {

     int x = ,t = ;

     char c = getchar();

     while((c > '' || c < '') && c != '-')

         c = getchar();

     if(c == '-')

         t = -,c = getchar();

     while(c >= '' && c <= '')

         x = x *  + c - ,c = getchar();

     bin x * t;

 }

 int tot,head[N],dep[N],ans;

 int n,m,a[N],S,T;

 //int cur[N];

 void write(int x)

 {

     if(x < )

         x = -x,putchar('-');

     if(x >= )

         write(x / );

     putchar(x %  + '');

 }

 struct EDGE

 {

     int val,to,next;

 }e[N];

 void add(int u,int v,int w)

 {

     e[++tot].to = v;

     e[tot].val = w;

     e[tot].next = head[u];

     head[u] = tot;

 }

 int BFS()

 {

     mt(dep,);

     queue<int>q;

     q.push(S);

     dep[S] = ;

     //zxy(i,1,100)

     //  cur[i] = head[i];

     while(!q.empty())

     {

     int u = q.front();

     q.pop();

     for(int i = head[u] ; i ; i = e[i].next)

     {

         int v = e[i].to;

         if(!dep[v] && e[i].val)

         {

         dep[v] = dep[u] + ;

         q.push(v);

         }

     }

     }

     return dep[T] != ;

 }

 int DFS(int st,int limit)

 {

     if(st == T)

     {

     ans += limit;

     bin limit;

     }

     if(!limit)

     bin ;

     int flow = ;

     for(int i = head[st] ; i ; i = e[i].next)

     {

 //    cur[st] = i;

     int v = e[i].to;

     if(dep[v] != dep[st] + )

         continue;

     int t = DFS(v,min(limit,e[i].val));

     if(t)

     {

         e[i].val -= t;

         e[i ^ ].val += t;

         flow += t;

         limit -= t;

         if(limit)

         break;

     }

     }

     if(!flow)

     dep[st] = -;

     return flow;

 }

 int main()

 {

     int b = ;

     mt(head,-);

     n = read(),m = read();

     S = ,T = n + m + ;

     zxy(i,,n)

     {

     add(i,S,);

     add(S,i,);

     }

     zxy(i,,n)

     {

     int op = read();

     if(op == )

         b++;

     zxy(j,,op)

     {

         int y = read();

         //cout<<"%"<<endl;

         add(i,y + n,);

         add(y + n,i,);

     }

     }

     zxy(i,,m)

     {

     add(n + i,T,);

     add(T,n + i,);

     }

     if(b !=  && n ==  && m == )

     {

     write();

     gameover;

     bin ;

     }

     while(BFS())

     while(DFS(S,INF));

     //cout<<1<<endl;

     write(ans);

     gameover;

     bin ;

 }

emmm……悄悄告诉你们一个神奇的事情，这题10个data，我就样例过不去（第三个data），哈哈…………嗝

巴特西

Luogu P1894 [USACO4.2]The Perfect Stall

最新文章

热门文章