Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
请大神们帮我看一下我的临界表到底拿错了?我该神邻接矩阵周,其他大框架基本没动,就AC了#include<stdio.h> #include<iostream> #include<string.h> #include<vector> using namespace std; int n,f,d; int liu[405][405]; int depth[405],s=0,t=403; vector<int>p[405]; int mins(int x,int y) { return (x<y)?x:y; } bool bfs() { //cout<<16<<endl; int que[409],head=1,tail=1; memset(depth,0,sizeof(depth)); que[tail++]=s; depth[s]=1; while(head<tail) { //cout<<23<<endl; for(int i=0;i<p[que[head]].size();i++) { int u=que[head],v=p[que[head]][i]; if(liu[u][v]>0&&depth[v]==0) { que[tail++]=v; depth[v]=depth[u]+1; } } head++; } if(depth[t]==0) return 0; //cout<<37<<endl; return 1; } int dfs(int x,int y) { //cout<<38<<endl; if(x==t) return y; for(int i=0;i<p[x].size();i++) { int v=p[x][i]; if(liu[x][v]>0&&depth[v]==depth[x]+1) { cout<<v<<endl; int di=dfs(v,mins(liu[x][v],y)); if(di>0) { liu[x][v]-=di; liu[v][x]+=di; return di; } } } return 0; } int main() { int ans=0; cin>>n>>f>>d; // cout<<s<<t<<endl; memset(liu,0,sizeof(liu)); for(int i=1;i<=n;i++) { int f1,d1; scanf("%d%d",&f1,&d1); p[i].push_back(i+300); liu[i][i+300]=1; for(int j=1;j<=f1;j++) { int x; scanf("%d",&x); p[100+x].push_back(i); liu[100+x][i]=1; } for(int k=1;k<=d1;k++) { int x; scanf("%d",&x); p[i+300].push_back(x+200); liu[i+300][x+200]=1; } } //cout<<85<<endl; for(int i=1;i<=f;i++) { p[s].push_back(100+i); liu[s][100+i]=1; } //cout<<92<<endl; for(int i=1;i<=d;i++) { p[i+200].push_back(t); liu[i+200][t]=1; } //cout<<98<<endl; while(bfs()) { while(int t=dfs(s,99999)) { ans+=t; } } cout<<ans<<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator