[HAOI2017]新型城市化
teafrogsf
2018-05-11 13:45:02
一道二分图好题啊......二分图最大匹配必须边问题。
考虑到一条必须边一定满足残量网络中满流并且边的端点不处在残量网络新图的一个$scc$里，因为如果处在一个$scc$里，那么可以沿着$scc$中的一个环增广来使得这条边不满流。
才发现码$\rm Dinic+Tarjan$如此费劲。
```cpp
#include<cstdio>
#include<queue>
#include<stack>
#include<algorithm>
#include<cstring>
#define neko 10010
#define meko 150010
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define travel(i,u,v) for(register int i=head[u],v=e[i].v;i;i=e[i].next,v=e[i].v)
using namespace std;
int n,m,S,T,inf=1e9;
int t=1;
typedef int arr[neko];
arr head,Head,cur,dis,col,scc,low,dfn;
template<typename T>
T chkmax(T a,T b)
{return a>b?a:b;}
template<typename T>
T chkmin(T a,T b)
{return a<b?a:b;}
struct node
{int u,v,cap,next;}e[meko<<2];
namespace Flow
{
void add(int x,int y,int z)
{
e[++t].v=y;
e[t].u=x;
e[t].cap=z;
e[t].next=head[x];
head[x]=t;
e[++t].v=x;
e[t].u=y;
e[t].cap=0;
e[t].next=head[y];
head[y]=t;
}
bool bfs()
{
queue<int>q;q.push(S);
memset(dis,0,sizeof(dis)),dis[S]=1;
int u;
while(!q.empty())
{
u=q.front(),q.pop();
travel(i,u,v)
{
if(!dis[v]&&e[i].cap)
{
dis[v]=dis[u]+1;
if(v==T)return 1;
q.push(v);
}
}
}return 0;
}
int dfs(int u,int flow)
{
if(u==T||(!flow))return flow;
int rescap=0,up;
for(register int &i=cur[u],v=e[i].v;i;i=e[i].next,v=e[i].v)
{
if(dis[v]==dis[u]+1&&(up=dfs(v,chkmin(e[i].cap,flow))))
{
e[i].cap-=up,e[i^1].cap+=up;
rescap+=up;
if(!(flow-=up))break;
}
}return rescap;
}
void dinic()
{int Ans=0;while(bfs())memcpy(cur,head,sizeof(cur)),Ans+=dfs(S,inf);}
}
struct notnode
{int u,v,next;}E[meko<<2];
struct AC
{int x,y;}ans[meko<<1];
namespace Tarjan
{
int p=0,cnt=0,x;
stack<int>s;
void dfs(int u)
{
dfn[u]=low[u]=++p;
s.push(u);
travel(i,u,v)
{
if(!e[i].cap)continue;
if(!dfn[v])dfs(v),low[u]=chkmin(low[u],low[v]);
else if(!scc[v])low[u]=chkmin(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++cnt,x=1e9;
while(x!=u)
{
x=s.top(),s.pop();
scc[x]=cnt;
}
}
}
}
namespace Solve
{
int t_2=0,now=0;
template<typename T>
void swap(T &x,T &y)
{T trs=x;x=y,y=trs;}
bool cmp(AC a,AC b)
{if(a.x==b.x)return a.y<b.y;return a.x<b.x;}
void add(int x,int y)
{
E[++t_2].u=x;
E[t_2].v=y;
E[t_2].next=Head[x];
Head[x]=t_2;
}
void dfs(int u,bool color)
{
col[u]=1<<color;
//printf("%d %d\n",u,color);
if(color)Flow::add(S,u,1);
else Flow::add(u,T,1);
for(register int i=Head[u],v=E[i].v;i;i=E[i].next,v=E[i].v)if((!col[v]))dfs(v,color^1);
}
void bipart()
{
f(i,1,n)if(!col[i])dfs(i,1);
for(register int i=1;i<=t_2;i+=2)
{
if(col[E[i].u]<col[E[i].v])swap(E[i].u,E[i].v);
Flow::add(E[i].u,E[i].v,1);
}
}
void countans()
{
//f(i,2,t)printf("%d %d %d\n",e[i].u,e[i].v,e[i].cap);
int u,v;
for(register int i=3;i<=t;i+=2)
{
if(e[i].cap)
{
u=e[i].u,v=e[i].v;
if(u>v)swap(u,v);
if(v==S||v==T)continue;
if(scc[u]^scc[v])ans[++now]=(AC){u,v};
}
}sort(ans+1,ans+now+1,cmp);
printf("%d\n",now);
f(i,1,now)printf("%d %d\n",ans[i].x,ans[i].y);
}
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
S=n+1,T=n+2;
f(i,1,m)
{
scanf("%d%d",&x,&y);
Solve::add(x,y),Solve::add(y,x);
}Solve::bipart(),Flow::dinic();
f(i,1,n+2)if(!dfn[i])Tarjan::dfs(i);
Solve::countans();
return 0;
}
```