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