题目
题解
给定的是个二分图，发现题目就是给定一张图的反图，要求在反图中删掉哪条边能使原图最大团大小增加
因为有定理$原图最大团=反图最大独立集=点数-最大匹配数$，所以现在要求的就是删掉哪条边能使最大匹配数减少，即此边是必选边
首先这条边$(u,v)$的反边必须满流，而且在残量网络上$u$和$v$不在同一个强连通分量里
我的理解是如果在同一个强连通分量里，说明可以不选这条边（即把这条边反由向变正向），把相对的另一条原来是正向的边反向（表示有流量通过）来保持结果不变……差不多这个理吧应该是
代码
# include<iostream>
# include<cstring>
# include<vector>
# include<cstdio>
# include<algorithm>
# define X first
# define Y second
# define mp make_pair
# define Pi pair<int,int>
using namespace std;
const int MAX=3e5+5;
struct p{
int x,y,d,id;
}c[MAX];
int n,m,num=1,Top,T,cnt,ans,tot;
int qu[MAX],dfn[MAX],st[MAX],col[MAX],low[MAX],d[MAX],h[MAX],H[MAX],ouo[MAX];
bool use[MAX];
vector<int> vec[MAX];
Pi _[MAX],__[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x,int y,int d,int id=0)
{
c[++num]=(p){h[x],y,d},h[x]=num;
c[++num]=(p){h[y],x,0,id},h[y]=num;
}
void Add(int x,int y) {vec[x].push_back(y),vec[y].push_back(x);}
void Bfs(int x)
{
int hl=1,tl=1;
qu[1]=x,ouo[x]=1;
while(hl<=tl)
{
int tt=qu[hl++];
for(int v:vec[tt])
if(!ouo[v]) ouo[v]=-ouo[tt],qu[++tl]=v;
}
}
bool bfs()
{
memset(d,0,sizeof(d));
int hl=1,tl=d[0]=1;
qu[1]=0;
while(hl<=tl)
{
int tt=qu[hl++];
for(int i=h[tt],y;i;i=c[i].x)
if(!d[y=c[i].y]&&c[i].d)
{
d[y]=d[tt]+1,qu[++tl]=y;
if(y==T) return 1;
}
}
return 0;
}
int dfs(int x=0,int dix=1e8)
{
if(x==T||!dix) return dix;
int sum=0;
for(int &i=H[x],dis,y;i;i=c[i].x)
if(d[y=c[i].y]==d[x]+1&&c[i].d)
{
dis=dfs(y,min(dix,c[i].d));
if(dis)
{
c[i].d-=dis,c[i^1].d+=dis,sum+=dis,dix-=dis;
if(!dix) break;
}
}
if(!sum) d[x]=-2;
return sum;
}
void Dinic()
{
int tot=0,D;
while(bfs())
{
memcpy(H,h,sizeof(H));
while(D=dfs()) tot+=D;
}
}
void Tarjan(int x)
{
low[x]=dfn[x]=++cnt,st[++Top]=x,use[x]=1;
for(int i=h[x],y;i;i=c[i].x)
if(c[i].d) if(!dfn[y=c[i].y]) Tarjan(y),low[x]=min(low[x],low[y]);
else if(use[y]) low[x]=min(low[x],dfn[y]);
if(low[x]==dfn[x])
{
int tt=-1;
++ans;
while(tt!=x) tt=st[Top--],use[tt]=0,col[tt]=ans;
}
}
int main()
{
n=read(),m=read(),T=n+1;
for(int i=1,x,y;i<=m;++i)
{
x=_[i].X=read(),y=_[i].Y=read();
if(x>y) swap(_[i].X,_[i].Y);
Add(x,y);
}
for(int i=1;i<=n;++i)
{
if(!ouo[i]) Bfs(i);
if(ouo[i]==1) add(0,i,1);
else add(i,T,1);
}
for(int i=1;i<=m;++i)
if(ouo[_[i].X]>ouo[_[i].Y]) add(_[i].X,_[i].Y,1,i);
else add(_[i].Y,_[i].X,1,i);
Dinic();
for(int i=0;i<=T;++i)
if(!dfn[i]) Tarjan(i);
for(int i=3;i<=num;i+=2)
if(!c[i].d) use[c[i].id]=1;
for(int i=1;i<=m;++i)
if(!use[i]) if(col[_[i].X]!=col[_[i].Y]) __[++tot]=_[i];
sort(__+1,__+1+tot),printf("%d\n",tot);
for(int i=1;i<=tot;++i)
printf("%d %d\n",__[i].X,__[i].Y);
return 0;
}
