【题目】1738: 最小路径覆盖问题
【题解】网络流
关于输出路径，因为即使有反向弧经过左侧点也一定会改变左侧点的去向，若没连向右侧就会被更新到0，所以不用在意。
mark记录有入度的右侧点，然后从没入度的右侧点开始把整条路径输出来即可。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=100000,inf=0x3f3f3f3f; int n,m,S,T,d[maxn],q[10010],first[maxn],tot=1,nex[maxn]; bool mark[maxn]; struct edge{int from,v,flow;}e[maxn]; void insert(int u,int v,int w) {tot++;e[tot].v=v;e[tot].flow=w;e[tot].from=first[u];first[u]=tot;tot++;e[tot].v=u;e[tot].flow=0;e[tot].from=first[v];first[v]=tot;} bool bfs() {memset(d,-1,4*(2*n+3));int head=0,tail=1;q[0]=S;d[S]=0;while(head<tail){int x=q[head++];if(head>10000)head=0;for(int i=first[x];i;i=e[i].from)if(e[i].flow&&d[e[i].v]==-1){int y=e[i].v;d[y]=d[x]+1;q[tail++]=y;if(tail>10000)tail=0;}}return d[T]!=-1; } int dinic(int x,int a) { // printf("x=%d a=%d\n",x,a);if(x==T||a==0)return a;int flow=0,f;for(int i=first[x];i;i=e[i].from)if(e[i].flow&&d[e[i].v]==d[x]+1&&(f=dinic(e[i].v,min(a,e[i].flow)))>0){if(f>0){nex[x]=e[i].v;if(e[i].v-n>0)mark[e[i].v-n]=1;}e[i].flow-=f;e[i^1].flow+=f;a-=f;flow+=f;if(a==0)break;}return flow; } int main() {scanf("%d%d",&n,&m);S=0,T=2*n+1;for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);insert(u,v+n,1);}for(int i=1;i<=n;i++)insert(S,i,1);for(int i=n+1;i<=2*n;i++)insert(i,T,1);int ans=n;while(bfs())ans-=dinic(S,inf);for(int i=1;i<=n;i++)if(!mark[i]){printf("%d ",i);int k=i;while(nex[k]){printf("%d ",nex[k]-n);k=nex[k]-n;}printf("\n");}printf("%d",ans);return 0; }
