Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么用vector存图,会re 改成矩阵就行了??

Posted by hccz95 at 2014-07-25 12:29:35 on Problem 1274
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator