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 |
为什么会wrong answer求助#include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<queue> using namespace std; #define maxn 1005 #define oo 999999999 int ans,N,F,D,cn[maxn][maxn],stp,enp,fa[maxn]; bool vis[maxn]; vector < int > adj[maxn]; queue < int > q; void in(); void work(); void out(); bool bfs(); int main() { // freopen("poj3281.in","r",stdin); // freopen("poj3281.out","w",stdout); in(); work(); out(); return 0; } void in() { scanf("%d%d%d",&N,&F,&D); stp=0;enp=N+F+D+1; for (int i = 1 ; i <= N ; ++i) { int fs,ds; scanf("%d%d",&fs,&ds); adj[i].push_back(i+N+D+F+1); cn[i][i+N+D+F+1]=1; for (int j = 0 ; j != fs ; ++j) { int a; scanf("%d",&a); adj[a+N].push_back(i); adj[i].push_back(a+N); cn[a+N][i]=oo; } for (int j = 0 ; j != ds ; ++j) { int a; scanf("%d",&a); adj[i+N+D+F+1].push_back(a+N+F); adj[a+N+F].push_back(i+N+D+F+1); cn[i+N+D+F+1][a+N+F]=oo; } } for (int i = N+1; i <=F+N;++i) { adj[stp].push_back(i); adj[i].push_back(stp); cn[stp][i]=1; } for (int i = F+N+1; i <=F+N+D;++i) { adj[i].push_back(enp); adj[enp].push_back(i); cn[i][enp]=1; } } void work() { while (bfs() == true) { int minf=oo; for (int u = enp ; fa[u] != -1 ; u=fa[u]) minf=min(minf,cn[ fa[u] ][u]); for (int u = enp ; fa[u] != -1 ; u=fa[u]) { cn[ fa[u] ][u]-=minf; cn[u][ fa[u] ]+=minf; } ans+=minf; } } void out() { printf("%d\n",ans); } bool bfs() { while ( !q.empty() ) q.pop(); memset(vis,false,sizeof(vis)); q.push(stp); vis[stp]=true; fa[stp]=-1; for ( ;!q.empty() ;q.pop() ) { int h =q.front(); for (int i = 0 ; i != adj[h].size() ; ++i) { int y =adj[h][i]; if (vis [y] || cn[h][y]==0 ) continue; vis[y]=true; q.push(y); fa[y]=h; if ( y == enp) return true; } } return false; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator