The Perfect Stall(最大ストリーム+図面作成)
2375 ワード
http://poj.org/problem?id=1274
标题:n頭牛m個の穀倉、1頭の牛はただ1個の固定的な穀倉産乳(牛はいくつかの穀倉が好き)に行きたいだけで、どれだけの頭牛が産内に行くことができるかを聞く
标题:最大流写、できるだけ穀倉を埋め尽くしてモデルを構築し、スーパーソーススーパーポイントを構築し、ソースポイントはすべての牛を接続することを考えています. 牛が好きな穀倉をつなぎ、 穀倉は合流点につながって、それから走ればいいです.
二分図も書けますが、できません.
标题:n頭牛m個の穀倉、1頭の牛はただ1個の固定的な穀倉産乳(牛はいくつかの穀倉が好き)に行きたいだけで、どれだけの頭牛が産内に行くことができるかを聞く
标题:最大流写、できるだけ穀倉を埋め尽くしてモデルを構築し、スーパーソーススーパーポイントを構築し、ソースポイントはすべての牛を接続することを考えています. 牛が好きな穀倉をつなぎ、 穀倉は合流点につながって、それから走ればいいです.
二分図も書けますが、できません.
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 20005;
const int INF = 0x3f3f3f3f;
bool vis[N];
struct Edge{
int to, cap, flow, next;
}edge[N*50];
int n, m, cnt;//n m cnt
int head[N];//
int dis[N];//
int cur[N];//
void add(int u, int v, int w){
edge[cnt] = (struct Edge){v, w, 0, head[u]};
head[u] = cnt++;
edge[cnt] = (struct Edge){u, 0, 0, head[v]};
head[v] = cnt++;
}
bool bfs(int start, int endd){//
memset(dis, -1, sizeof(dis));
memset(vis, false, sizeof(vis));
queueque;
dis[start] = 0;
vis[start] = true;
que.push(start);
while(!que.empty()){
int u = que.front();
que.pop();
for(int i = head[u]; i != -1; i = edge[i].next){
Edge E = edge[i];
if(!vis[E.to] && E.flow0){
edge[i].flow += f;
edge[i^1].flow -= f;
flow += f;
res -= f;
if(res == 0) break;
}
}
}
return flow;
}
int max_flow(int start, int endd){
int flow = 0;
while(bfs(start, endd)){
memcpy(cur, head, sizeof(head));//
flow += dfs(start, INF, endd);
}
return flow;
}
void init(){//
cnt = 0;
memset(head, -1, sizeof(head));
}
int main(){
int na,nb;
while(cin>>na>>nb){
init();
int sp=0;//
int tp=na+nb+1;//
for(int i=1;i<=na;i++){
add(sp,i,1);//
int k;
cin>>k;
for(int j=1;j<=k;j++){
int x;
cin>>x;
add(i,na+x,1);//
}
}
for(int j=1;j<=nb;j++){
add(na+j,tp,1);//
}
int ans=max_flow(sp,tp);
cout<