BZOJ 3546: [ONTAK2010]Life of the Party

Description

一个二分图最大匹配,求出所有关键点.\(n,m\leqslant 10^4,k\leqslant 10^5\)

Solution

二分图匹配.

2015年国家队论文集 - 浅谈图的匹配算法及其应用 陈胤伯

Code

/**************************************************************
    Problem: 3546
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:1844 ms
    Memory:14436 kb
****************************************************************/
 
#include 
using namespace std;
 
#define mpr make_pair
 
const int N = 20050;
const int M = 100050;
const int oo = 0x3fffffff;
 
inline int in(int x=0,char s=getchar()) { while(s>'9'||s<'0')s=getchar();
    while(s>='0'&&s<='9')x=x*10+s-'0',s=getchar();return x; }
 
struct Network {
    struct Edge { int fr,to,fl; }edge[M<<3];
    vector g[N];
    int S,T,flow,ce,k;
    int d[N],p[N],cur[N];
     
    void AddEdge(int fr,int to,int fl) {
        edge[ce++]=(Edge) { fr,to,fl },edge[ce++]=(Edge) { to,fr,0 };
        g[fr].push_back(ce-2),g[to].push_back(ce-1);
    }
    int BFS() {
        memset(d,0xff,sizeof(d));
        queue q;
        d[S]=0,q.push(S);
        for(int x;!q.empty();) {
            x=q.front(),q.pop();
            for(int i=0;i<(int)g[x].size();i++) {
                Edge &e=edge[g[x][i]];
                if(e.fl && d[e.to]==-1) d[e.to]=d[x]+1,q.push(e.to);
            }
        }return d[T]!=-1;
    }
    int Dinic() {
        for(int x;BFS();) {
            for(k=0,x=S,memset(cur,0,sizeof(cur));;) {
                if(x==T) {
                    int mine=0,minf=oo;
                    for(int i=0;i g[N];
    int vis[N];
     
    void clr() { memset(vis,0,sizeof(vis));for(int i=0;i ";
            for(int j=0;j<(int)g[i].size();j++) cout< pr[N];
int L[N];
 
int main() {
    n=in(),m=in(),k=in();
    for(int i=1;i<=k;i++) {
        int u=in(),v=in();
        py.AddEdge(u,v+n,1);
    }
    py.S=0,py.T=n+m+1;
    for(int i=1;i<=n;i++) py.AddEdge(py.S,i,1);
    for(int i=1;i<=m;i++) py.AddEdge(i+n,py.T,1);
    py.Dinic();
//  cout<