BZOJ 3546 Life of the Party(ダイバーシチマッチング-最大ストリーム)

タイトルリンク:http://www.lydsy.com:808/JudgeOnline/problem.php?id=3546
題意:二分図を与える.(ABの2つの集合の点はn,m),辺はK個である.どの点を削除すると最大マッチングが減少するかを尋ねます.
構想:まず図を建てて最大の流れを走る.そしてsから一度dfsを開始し,B集合中の点xまで走ることができれば,xがA集合中のある点にマッチできることを示し,x削除しても構わない.tからdfsを1回、同様にs中のyに到達すれば、y削除しても構わない.

const int INF=1000000005;

const int N=20005;





struct node

{

    int v,next,cap;

};

    

    

node edges[N*20];

int head[N],e;

int curedge[N];

    

    

inline void add(int u,int v,int cap)

{

    edges[e].v=v;

    edges[e].cap=cap;

    edges[e].next=head[u];

    head[u]=e++;

}

    

    

inline void Add(int u,int v,i64 cap)

{

    add(u,v,cap);

    add(v,u,0);

}

   

int dis[N];

   

   

int Q[N];



int bfs(int s,int t)

{

    clr(dis,-1);

    int i;

    for(i=s;i<=t;i++) curedge[i]=head[i];

    int L=0,R=0;

   

    dis[s]=0;

    Q[R++]=s;

   

    while(L<R)

    {

        int u=Q[L++];

   

        for(i=head[u];i!=-1;i=edges[i].next)

        {

            if(edges[i].cap&&-1==dis[edges[i].v])

            {

                dis[edges[i].v]=dis[u]+1;

                Q[R++]=edges[i].v;

                if(edges[i].v==t) return 1;

            }

        }

    }

    return 0;

}

   

   

   

int DFS(int u,int det,int t)

{

    if(u==t) return det;

    int now=0;

    int i;

    for(int &i=curedge[u];i!=-1&&det;i=edges[i].next)

    {

        int v=edges[i].v;

        int w=edges[i].cap;

        if(w&&dis[u]+1==dis[v])

        {

            int tmp=DFS(v,min(w,det),t);

            if(tmp==0) continue;

            edges[i].cap-=tmp;

            edges[i^1].cap+=tmp;

            now+=tmp;

            det-=tmp;

        }

    }

    return now;

}

   

int dinic(int s,int t)

{

    int ans=0;

    while(bfs(s,t)) ans+=DFS(s,INF,t);

    return ans;

}



int n,m,K;





int visit[N][2];

int f[N];





int SS,TT;



void dfs(int u,int c)

{

	visit[u][c]=1;

	if(c==0&&u<=n||c==1&&u>n) f[u]=1;

	else f[u]=0;

	int i;

	for(i=head[u];i!=-1;i=edges[i].next)

	{

		int v=edges[i].v;

		if(edges[i^c].cap>0&&!visit[v][c]&&v!=SS&&v!=TT) 

		{

			dfs(v,c);

		}

	}

}



int main()

{



	n=getInt();

	m=getInt();

	K=getInt();

	clr(head,-1);

	int s=0,t=n+m+1;

	int i;

	for(i=1;i<=n;i++) Add(s,i,1);

	for(i=1;i<=m;i++) Add(i+n,t,1);

	for(i=1;i<=K;i++)

	{

		int x=getInt();

		int y=getInt();

		Add(x,y+n,1);

	}

	dinic(s,t);

	SS=s;

	TT=t;

	dfs(s,0); dfs(t,1);

	for(i=1;i<=n;i++) if(!f[i]) printf("%d
",i); 

	for(i=1;i<=m;i++) if(!f[i+n]) printf("%d
",i); 

}