记录编号	59140	评测结果	AAAAAAAAAAA
题目名称	728.[网络流24题] 最小路径覆盖问题	最终得分	100
用户昵称	SpaceQ	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2013-05-03 20:31:45	内存使用	0.32 MiB

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
#include<string>
#include<algorithm>
#include<sstream>
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define maxn 500
using namespace std;
const int inf =~0u>>2;

struct edge
{
	int from,to,cap,flow;
};
vector<int>G[maxn];
vector<edge>E;
int cur[maxn],d[maxn],s,t;
void add(int from,int to,int cap)
{
	E.pb((edge){from,to,cap,0});
	E.pb((edge){to,from,0,0});
	int m=E.size();
	G[from].pb(m-2);
	G[to].pb(m-1);
}

queue<int>Q;
bool mklevel()
{
	memset(d,63,sizeof(d));	
	Q.push(s);
	d[s]=0;	
	while(Q.size())
	{
		int x=Q.front();Q.pop();
		rep(i,G[x].size())
		{
			edge&e=E[G[x][i]];
			if(d[e.to]>maxn && e.cap>e.flow)
			{
				d[e.to]=d[x]+1;
				Q.push(e.to);
			}
		}
	}
	return d[t]<maxn;
}
int dfs(int x,int a)
{
	if(x==t||a==0)return a;
	int f,flow=0;
	repd(i,G[x].size())
	{
		edge&e=E[G[x][i]];
		if(d[e.to]!=d[x]+1)continue;
		f=dfs(e.to,min(a,e.cap-e.flow));
		if(f>0)
		{
			e.flow+=f;
			E[G[x][i]^1].flow-=f;
			flow+=f;
			a-=f;
			if(a==0)break;
		}
	}
	return flow;
}
int dinic()
{
	int flow=0;
	while(mklevel())
	{
		memset(cur,0,sizeof(cur));
		flow+=dfs(s,inf);
	}
	return flow;
}


int nex[maxn];
vector<int> st;
int main()
{
    freopen("path3.in","r",stdin);
    freopen("path3.out","w",stdout);
    int n,m,a,b;
    scanf("%d%d",&n,&m);
    s=0;t=n+n+1;
    while(m--)
    {
        scanf("%d%d",&a,&b);
        add(a,b+n,1);
    }
    for(int i=1;i<=n;i++)add(s,i,1);
    for(int i=n+1;i<=n+n;i++)add(i,t,1);
    int ans=n-dinic();
    
    memset(nex,0,sizeof(nex));
    for(int i=1;i<=n;i++)
    {
        rep(j,G[i].size())
        {
            edge&e=E[G[i][j]];
            if(e.flow==1)
            {
                nex[i]=e.to-n;
                //printf("%d->%d\n",i,e.to-n);
                break;
            }
        }
    }
    //for(int i=1;i<=n;i++)printf("%d->%d\n",i,nex[i]);
    
    for(int i=n+1;i<=n+n;i++)
    {
        rep(j,G[i].size())
        {
            edge&e=E[G[i][j]];
            if(e.cap>0 && e.cap!=e.flow)
            {
                st.pb(i-n);
                break;
            }
        }
        //if(G[i].size()==0)continue;
        //edge&e=E[G[i][0]];
        //if(e.flow==0)st.pb(i-n);
    }
    rep(i,st.size())
    {
        printf("%d",st[i]);
        int p=nex[st[i]];
        while(p!=0)
        {
            printf(" %d",p);
            p=nex[p];
        }
        putchar('\n');
    }
    printf("%d\n",ans);
    return 0;
}