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-ing

Posted by ccsu2008021220 at 2009-12-05 20:30:34 on Problem 1815
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int Max=404;
const int INF=1<<30;
int map[Max][Max],c[Max][Max];
int ans[Max];
int queue[Max],pre[Max];
void built_Graph(int n)
{
     memset(map,0,sizeof(map));
     for(int i=1;i<=n;i++)
     {
             map[i*2-1][i*2]=map[i*2][i*2-1]=1;
             for(int j=1;j<=n;j++)
                 if(c[i][j])
                     map[i*2][j*2]=INF;
     }
}
int bfs(int s,int t,int n)
{
    int head=0,tail=0;
    queue[tail++]=s;
    //cout<<"queue "<<queue[head]<<endl;
    memset(pre,-1,sizeof(pre));
    while(head<tail)
    {
         int u=queue[head++];
        // cout<<"queue "<<u<<endl;
         for(int i=1;i<=n;i++)
         {
            // cout<<u<<" "<<i<<" "<<c[u][i]<<" pre "<<pre[i]<<endl;
             if(c[u][i]>0&&pre[i]==-1)
             {
                   queue[tail++]=i;
                  // cout<<i<<endl;
                   pre[i]=u;
                   if(i==t) break;
             }
         }
    }
    if(pre[t]==-1) return 0;
    int delta=INF;
    for(int i=t;i!=s;i=pre[i])
       delta=min(delta,c[pre[i]][i]);
    if(delta==INF) return 0;
    else return delta;
}
int max_flow(int s,int t,int n)
{
     int flow=0;
     while(1)
     {
             int delta=bfs(s,t,n);
             //cout<<delta<<endl;
             if(delta==0) break;
             flow+=delta;
             for(int i=t;i!=s;i=pre[i])
             {     //cout<<i<<" ";
                     c[pre[i]][i]-=delta;
                     c[i][pre[i]]+=delta;
             }//cout<<endl;
     }
     return flow;
}
int main()
{
    int n,s,t;
    while(scanf("%d%d%d",&n,&s,&t)!=EOF)
    {
          memset(ans,0,sizeof(ans));
          memset(c,0,sizeof(c));
          for(int i=1;i<=n;i++)
              for(int j=1;j<=n;j++)
                      scanf("%d",&c[i][j]);
          if(c[s][t])
          {
              printf("NO ANSWER!\n");
              continue;
          }
          built_Graph(n);
          memcpy(c,map,sizeof(map));
          int F=max_flow(s,t,2*n);
          //cout<<"flow "<<F<<endl;
          int num=0;
          for(int i=1;i<=n;i++)
              if(i!=s&&i!=t)
              {
                   memcpy(c,map,sizeof(map));
                   c[i*2-1][i*2]=c[i*2][i*2-1]=0;
                   int temp;
                   if((temp=max_flow(s,t,2*n))!=F)
                   {
                        //cout<<"flow "<<temp<<endl;
                        map[i*2-1][i*2]=map[i*2][i*2-1]=0;
                        ans[++num]=i;
                        F--;
                   }
              }
          if(num==0)
          {
                    printf("%d\n",0);
                    continue;
          }
          printf("%d\n",num);
          for(int i=1;i<=num;i++)
          {
              if(i>1) printf(" ");
              printf("%d",ans[i]);
          }
          printf("\n");
    }
    return 0;
}

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