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 |
为什么用vector存图,会re 改成矩阵就行了??#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<set> #include<stack> #include<map> #define sf scanf #define pf printf #define pb push_back #define Fill(a, x) memset(a, x, sizeof(a)) #define rep(i, a, b) for (int i=a; i<=b; i++) #define sqr(x) ((x)*(x)) #define two(x) (1<<x) #define modP 1000000007 //#define maxM 200 #define maxN 5000 typedef long long LL; using namespace std; int N, M; int mx[maxN+2], my[maxN+2]; int dx[maxN+2], dy[maxN+2]; int vis[maxN+2]; vector<int> son[maxN+2]; queue<int> que; int Find(int u){ rep(i, 0, son[u].size()-1){ int v=son[u][i]; if (!vis[v] && dy[v]==dx[u]+1){ vis[v]=1; if (!my[v] || Find(my[v])){ mx[u]=v; my[v]=u; return 1; } } } return 0; } int Match(){ Fill(mx, 0); Fill(my, 0); int ans=0; while(1){ int flag=0; while (!que.empty()) que.pop(); Fill(dx, 0); Fill(dy, 0); rep(i, 1, N) if (!mx[i]) que.push(i); while (!que.empty()){ int u=que.front(); que.pop(); rep(i, 0, son[u].size()-1){ int v=son[u][i]; if (dy[v]) continue; dy[v]=dx[u]+1; if (my[v]){ dx[my[v]]=dy[v]+1; que.push(my[v]); } else flag=1; } } if (!flag) break; Fill(vis, 0); rep(i, 1, N) if (!mx[i] && Find(i)) ans++; } return ans; } int main(){ while (sf("%d%d", &N, &M)!=EOF){ int o, u; rep(i, 1, N){ son[i].clear(); sf("%d", &o); while (o--){ sf("%d", &u); son[i].pb(u); } } pf("%d\n", Match()); } return 0; } //Runtime Error Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator