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 |
先匹配 在枚举点 为什么wa#include <iostream> using namespace std; #define MN 1005 bool graph[MN][MN];//graph[x][y] int yMatch[MN], xMatch[MN]; bool vis[MN]; int nx, ny; int dfs(int v) { int i; for(i=1; i<=ny; i++) if( graph[v][i] &&!vis[i]) { vis[i]=true; if( yMatch[i]==0 || dfs(yMatch[i])) { yMatch[i]=v; xMatch[v]=i; return 1; } } return 0; } int maxMatch() { int i, ans=0; memset(yMatch, 0, sizeof(yMatch)); memset(xMatch, 0, sizeof(xMatch)); for(i=1; i<=nx; i++) { memset(vis, false, sizeof(vis)); ans+=dfs(i); } return ans; } int g[MN][MN]; int aa[MN],bb[MN]; int n; int pu[MN]; int main() { int m; cin>>n>>m; int i; for(i=1;i<=n;++i)cin>>aa[i]; for(i=1;i<=n;++i)cin>>bb[i]; memset(g,0,sizeof(g)); while(m--) { int s,t; cin>>s>>t; g[s][t]++; } int j; memset(graph,0,sizeof(graph)); for(i=1;i<=n;++i) { for(j=1;j<=n;++j) { if(g[i][j])graph[i][j]=true; } } nx=ny=n; int mm=maxMatch(); int f=0,ans=0; for(i=1;i<=n;++i) { if(bb[i]<aa[xMatch[i]]) { pu[f++]=-i; ans+=bb[i]; } else { pu[f++]=xMatch[i]; ans+=aa[xMatch[i]]; } } cout<<ans<<endl<<mm<<endl; for(i=0;i<f;++i) { if(pu[i]>0) { cout<<pu[i]<<" +\n"; } else { cout<<-pu[i]<<" -\n"; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator