Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

百度了下,构图有点大问题,可又给WA掉了两次

Posted by yuanchuanshun at 2010-07-30 19:49:42 on Problem 3281
要改成两排牛, 这个我接受。。
且容量改为1,牛到食物那里写INT——MAX不行吗,非得1吗??



#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#define intmax 200000000
#define arr 405
using namespace std;
int N,F,D,S,T;
int pre[arr],flow[arr],map[arr][arr];
int BFS()
{
    int i,v,u;
    for(i=S;i<=T;i++) pre[i]=-1,flow[i]=intmax;
    //memset(pre,-1,sizeof(pre));
    //memset(flow,intmax,sizeof(flow));
    //如果用上面那两行的话就出不了结果; 
    pre[S]=0;
    queue<int>que;
    que.push(S);
    while(!que.empty())
    {
         v=que.front();
         que.pop();
         for(u=1;u<=T;u++)
         {
             if(pre[u]!=-1||map[v][u]==0) continue;
             pre[u]=v;
             flow[u]=min(flow[v],map[v][u]);
             que.push(u);
         }
    }
    if(flow[T]==intmax) return -1;
    else return flow[T];
}
int EK()
{
    int temp,now,last,ans=0;
    while(1)
    {
        temp=BFS();
        if(temp==-1) break;
        ans+=temp;
        now=T;
        while(now!=S)
        {
           last=now; now=pre[now];
           map[now][last]-=temp;
           map[last][now]+=temp;
        }
    }
    return ans;
}
int main()
{
    int i,j,num_F,num_D,t;
    while(cin>>N>>F>>D) //N+F+D<=300;
    {
        S=0; T=N+F+D+1;
        memset(map,0,sizeof(map));
        for(i=1;i<=F;i++) map[S][i]=1;
        for(i=1;i<=D;i++) map[i+F+N][T]=1;
        for(i=1;i<=N;i++)
        {
            scanf("%d%d",&num_F,&num_D);
            for(j=1;j<=num_F;j++)
            {
                scanf("%d",&t);
                map[t][i+F]=1;
            }
            for(j=1;j<=num_D;j++)
            {
                scanf("%d",&t);
                map[i+F+N][t+F+N+N]=1;
            }
        }
        for(i=1+F;i<=N+F;i++)
        map[i][i+N]=1;
        int ans=EK();
        cout<<ans<<endl;
    }
}    
/*
4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3
Sample Output
3
*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator