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),哈哈…………嗝

上一篇:自动改变html font-size,实现移动端rem适配


下一篇:BeanFactory 使用控制反转 (IOC) 模式将应用程序的配置和依赖性规范与实际的应用程序代码分开。面向切面 将声明性事务管理集成到应用程序中