RT,WA了十几次了
还是不过
#include<bits/stdc++.h>
#define INF 0x7f
using namespace std;
struct edge
{
int from,to,cap,flow;
};
struct edge2
{
int to,w;
};
int n,s,t,deg[150];
int ans,cnt,d[150],cur[150],cnt2,tot;
int route[150];
bool vis[150],b;
vector<edge>e;
vector<edge2>e2;
vector<int>v[150];
vector<int>v2[150];
void read(int& x)
{
char c=getchar();
x=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
}
void link(int from,int to,int cap)
{
e.push_back((edge){from,to,cap,0});
e.push_back((edge){to,from,0,0});
cnt=e.size();
v[from].push_back(cnt-2);
v[to].push_back(cnt-1);
}
void link2(int from,int to,int w)
{
e2.push_back((edge2){to,w});
cnt2=e2.size();
v2[from].push_back(cnt2-1);
}
bool bfs()
{
queue<int>q;
memset(vis,0,sizeof(vis));
d[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int fa=q.front();
q.pop();
for(unsigned int i=0; i<v[fa].size(); i++)
{
edge& ed=e[v[fa][i]];
if(!vis[ed.to]&&ed.cap>ed.flow)
{
vis[ed.to]=1;
d[ed.to]=d[fa]+1;
q.push(ed.to);
}
}
}
return vis[t];
}
int dfs(int x,int a)
{
if(x==t||!a)return a;
int flow=0,f;
for(int& i=cur[x]; i<v[x].size(); i++)
{
edge& ed=e[v[x][i]];
if(d[ed.to]==d[x]+1&&(f=dfs(ed.to,min(a,ed.cap-ed.flow)))>0)
{
flow+=f;
ed.flow+=f;
e[v[x][i]^1].flow-=f;
a-=f;
if(!a)break;
}
}
return flow;
}
int dinic()
{
int maxflow=0;
while(bfs())
{
memset(cur,0,sizeof(cur));
maxflow+=dfs(s,INF);
}
return maxflow;
}
void print(int x)
{
route[++tot]=x;
bool ok=0;
for(unsigned int i=0; i<v2[x].size(); i++)
{
edge2& ed2=e2[v2[x][i]];
if(b)return ;
if(ed2.w)
{
ok=1;
ed2.w--;
print(ed2.to);
}
}
if(!ok)
{
deg[x]--;
b=1;
}
}
int main()
{
while(scanf("%d",&n)==1)
{
e.clear();
e2.clear();
memset(deg,0,sizeof(deg));
ans=0;
s=0;
t=n+1;
v[s].clear();
v[t].clear();
v2[s].clear();
v2[t].clear();
for(int i=1;i<=n;i++)
{
v[i].clear();
v2[i].clear();
}
for(int i=1; i<=n; i++)
{
int num;
read(num);
while(num--)
{
int x;
read(x);
deg[x]++;
deg[i]--;
link(i,x,INF);
}
}
for(int i=1; i<=n; i++)
{
if(deg[i]<0)
{
link(i,t,-deg[i]);
ans-=deg[i];
}
else if(deg[i]>0)link(s,i,deg[i]);
}
ans-=dinic();
printf("%d\n",ans);
for(int i=0; i<e.size(); i+=2)
{
edge& ed=e[i];
if(e[i].from==s||e[i].to==s||e[i].to==t||e[i].from==t)continue;
link2(ed.from,ed.to,e[i].flow+1);
deg[ed.from]-=ed.flow;
deg[ed.to]+=ed.flow;
}
for(int i=1; i<=n; i++)
{
while(deg[i]<0)
{
tot=b=0;
deg[i]++;
print(i);
printf("%d",route[1]);
for(int j=2;j<=tot;j++)printf(" %d",route[j]);
putchar('\n');
}
}
}
}