bzoj3546: [ONTAK2010]Life of the Party

传送门

#include <bits/stdc++.h>
using namespace std;

#define mpr make_pair

const int N = ;
const int M = ;
const int oo = ;

inline int in(int x=,char s=getchar()) { while(s>'9'||s<'0')s=getchar();
    while(s>='0'&&s<='9')x=x*+s-'0',s=getchar();return x; }

struct Network {
    struct Edge { int fr,to,fl; }edge[M<<];
    vector<int> 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, };
        g[fr].push_back(ce-),g[to].push_back(ce-);
    }
    int BFS() {
        memset(d,,sizeof(d));
        queue<int> q;
        d[S]=,q.push(S);
        for(int x;!q.empty();) {
            x=q.front(),q.pop();
            for(int i=;i<(int)g[x].size();i++) {
                Edge &e=edge[g[x][i]];
                if(e.fl && d[e.to]==-) d[e.to]=d[x]+,q.push(e.to);
            }
        }return d[T]!=-;
    }
    int Dinic() {
        for(int x;BFS();) {
            for(k=,x=S,memset(cur,,sizeof(cur));;) {
                if(x==T) {
                    int mine=,minf=oo;
                    for(int i=;i<k;i++) if(edge[p[i]].fl<minf) minf=edge[p[i]].fl,mine=i;
                    for(int i=;i<k;i++) edge[p[i]].fl-=minf,edge[p[i]^].fl+=minf;
                    k=mine,x=edge[p[mine]].fr,flow+=minf;
                }
                for(int &i=cur[x];i<(int)g[x].size();i++) {
                    Edge &e=edge[g[x][i]];
                    if(e.fl && d[e.to]==d[x]+) break;
                }if(cur[x]<(int)g[x].size()) {
                    p[k++]=g[x][cur[x]],x=edge[g[x][cur[x]]].to;
                } else {
                    if(!k) break;
                    d[x]=-,x=edge[p[--k]].fr;
                }
            }
        }return flow;
    }
}py;

struct Gph {
    vector<int> g[N];
    int vis[N];

    void clr() { memset(vis,,sizeof(vis));for(int i=;i<N;i++) g[i].clear(); }
    void AddEdge(int fr,int to) { g[fr].push_back(to); }
    void DFS(int u) {
        if(vis[u]) return;vis[u]=;
        for(int i=;i<(int)g[u].size();i++) DFS(g[u][i]);
    }
    void outE(int n) {
        for(int i=;i<=n;i++) {
            cout<<i<<" --> ";
            for(int j=;j<(int)g[i].size();j++) cout<<g[i][j]<<" ";cout<<endl;
        }
    }
}pn;

int n,m,k,cp;
pair<int,int> pr[N];
int L[N];

int main() {
    n=in(),m=in(),k=in();
    for(int i=;i<=k;i++) {
        int u=in(),v=in();
        py.AddEdge(u,v+n,);
    }
    py.S=,py.T=n+m+;
    for(int i=;i<=n;i++) py.AddEdge(py.S,i,);
    for(int i=;i<=m;i++) py.AddEdge(i+n,py.T,);
    py.Dinic();
//  cout<<py.Dinic()<<endl;
    for(int i=;i<*k;i+=) if(py.edge[i^].fl)
        pr[++cp]=mpr(py.edge[i].fr,py.edge[i].to);
//  cout<<"---"<<endl;

    memset(L,,sizeof(L));
    for(int i=;i<=cp;i++) L[pr[i].first]=pr[i].second;
    for(int i=;i<*k;i+=) {
        if(L[py.edge[i].fr]!=py.edge[i].to) pn.AddEdge(py.edge[i].fr,py.edge[i].to);
        else pn.AddEdge(py.edge[i].to,py.edge[i].fr);
    }
    for(int i=;i<=n;i++) if(!L[i]) pn.DFS(i);
    for(int i=;i<=n;i++) if(!pn.vis[i]) printf("%d\n",i);

//  pn.outE(n+m);
//  cout<<"---"<<endl;
    pn.clr();
    memset(L,,sizeof(L));
    for(int i=;i<=cp;i++) L[pr[i].second]=pr[i].first;
    for(int i=;i<*k;i+=) {
        if(L[py.edge[i].fr]!=py.edge[i].to) pn.AddEdge(py.edge[i].fr,py.edge[i].to);
        else pn.AddEdge(py.edge[i].to,py.edge[i].fr);
    }
    for(int i=;i<=m;i++) if(!L[i+n]) pn.DFS(i+n);
    for(int i=;i<=m;i++) if(!pn.vis[i+n]) printf("%d\n",i);
//  pn.outE(n+m);
    return ;
}