[题解]poj 1274 The Perfect Stall(网络流)

二分匹配传送门[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 ;
}
上一篇:今天发现之前瑞乐做的登录和注册居然都是用的get请求,瞬间出了一身冷汗.


下一篇:spring事物传播机制与隔离级别