题目分析:
这题出的好!
首先问题肯定是二分图的最大独立集, 如果删去某条匹配边之后独立集是否会变大.
跑出最大流之后流满的边就是匹配边.
如果一个匹配边的两个端点在一个强连通分量里, 那这条边删掉之后我们就可以找到一个替代方案使得匹配不变小.
具体的, 假设这两个点是 x,y. 因为两者之间连的是匹配边, 那么存在一个路径从 t->y->x->s. 那只要从 s 有另一条路径到 y 或者从 x 有另一条路径到 t 那就构成一个强连通分量, 我们只考虑 s 到 y 的情况.
如果存在一条这样的路, 我们会发现每次从 X 集合跳到 Y 集合的时候走的是黑边, 从 Y 集合跳到 X 集合的时候走的是红遍, 因为我们的目标节点在 Y 集合, 所以采用匈牙利树的分析方法, 黑边总比红边多 1, 所以可以把这条路径翻转达到我们的目的.
代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int maxm = 400000,maxn = 20300;
- struct edge{int from,to,flow;}edges[maxm];
- int num,n,m,arr[maxn];
- vector <int> g[maxn];
- int color[maxn];
- namespace BioGraph{
- vector<int> T[maxn];
- queue<int> Q;
- void pd(){
- for(int i=1;i<=n;i++){
- if(arr[i]) continue;
- Q.push(i); arr[i] = 1; color[i] = 0;
- while(!Q.empty()){
- int k = Q.front(); Q.pop();
- for(int i=0;i<T[k].size();i++){
- int z = T[k][i];
- if(arr[z]) continue;
- Q.push(z); color[z] = (color[k]^1); arr[z] = 1;
- }
- }
- }
- }
- }
- namespace SCC{
- int dfn[maxn],low[maxn],scc[maxn],sccnum,cl;
- stack<int> sta;
- void Tarjan(int now){
- low[now] = dfn[now] = ++cl;
- sta.push(now);
- for(int i=0;i<g[now].size();i++){
- if(edges[g[now][i]].flow == 0) continue;
- int to = edges[g[now][i]].to;
- if(arr[to]) continue;
- if(dfn[to]) low[now] = min(low[now],dfn[to]);
- else{Tarjan(to);low[now] = min(low[now],low[to]);}
- }
- if(low[now]==dfn[now]){
- sccnum++;
- while(true){
- int pi = sta.top(); sta.pop();
- arr[pi] = 1; scc[pi] = sccnum;
- if(now == pi) break;
- }
- }
- }
- }
- void AddEdge(int x,int y,int v){
- edges[num++] = (edge){x,y,v};
- edges[num++] = (edge){y,x,0};
- g[x].push_back(num-2);
- g[y].push_back(num-1);
- }
- int dis[maxn],cur[maxn];
- queue<int> qq;
- int BFS(){
- qq.push(0); memset(dis,-1,sizeof(dis)); dis[0] = 1;
- while(!qq.empty()){
- int k = qq.front(); qq.pop();
- for(int i=0;i<g[k].size();i++){
- edge sm = edges[g[k][i]];
- if(sm.flow && dis[sm.to]== -1){
- dis[sm.to] = dis[k]+1;
- qq.push(sm.to);
- }
- }
- }
- return dis[n+1];
- }
- int dfs(int x,int a){
- if(x == n+1 || a == 0) return a;
- int flow = 0,f;
- for(int &i=cur[x];i<g[x].size();i++){
- edge &xx = edges[g[x][i]];
- if(dis[xx.to]>dis[x]&&(f=dfs(xx.to,min(a,xx.flow)))){
- xx.flow -= f;
- flow += f;
- a -= f;
- edges[g[x][i]^1].flow+=f;
- if(a == 0) return flow;
- }
- }
- return flow;
- }
- void read(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++){
- int x,y; scanf("%d%d",&x,&y);
- BioGraph::T[x].push_back(y);
- BioGraph::T[y].push_back(x);
- }
- BioGraph::pd();
- for(int i=1;i<=n;i++){
- if(color[i]) {AddEdge(i,n+1,1);continue;}
- else AddEdge(0,i,1);
- for(int j=0;j<BioGraph::T[i].size();j++){
- int z = BioGraph::T[i][j];
- AddEdge(i,z,1);
- }
- }
- }
- vector<pair<int,int>> res;
- void work(){
- int flow = 0;
- while(BFS() != -1){
- memset(cur,0,sizeof(cur));
- flow += dfs(0,19260817);
- }
- memset(arr,0,sizeof(arr));
- for(int i=0;i<=n+1;i++){
- if(arr[i]) continue;
- SCC::Tarjan(i);
- }
- for(int i=0;i<num;i++){
- if(edges[i].from == 0 || edges[i].to == n+1) continue;
- if(edges[i].from == n+1 || edges[i].to == 0) continue;
- if(color[edges[i].from]) continue;
- if(edges[i].flow) continue;
- if(SCC::scc[edges[i].from] == SCC::scc[edges[i].to]) continue;
- int x=min(edges[i].from,edges[i].to),y=max(edges[i].from,edges[i].to);
- res.push_back(make_pair(x,y));
- }
- sort(res.begin(),res.end());
- int z = res.size(); printf("%d\n",z);
- for(int i=0;i<z;i++){ printf("%d %d\n",res[i].first,res[i].second); }
- }
- int main(){
- read();
- work();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2988234.html