题意很简单：
给出一张有向图，每次你可以从图中的任意一点出发，经过若干条边后停止，然后问你最少走几次可以将图中的每条边都走过至少一次，并且要输出方案
这个转化为网络流的话，就相当于 求一个最小流，并且存在下界，即每条边至少走一次
这让我联想到很久之前的一道题，也是有向图，问走多少条路径可以将整个图中的每条边都走过，但是跟本题不同的是，那题是不允许重复走边的。
那道题目的解是这样的：
对于图中的每个点i，设D[i]为(i的入度-i的出度)的值，按照D[i]将图中的点分类：D[i]<0的称为“入少出多”的点，D[i]>0的称为“出少入多”的点，D[i]=0的称为“入出相等”的点。则有：
定理 有向无环图中最小边路径覆盖的值等于图中所有“入少出多”的点的D值之和。
证明：
其实只需证明：对于一个至少有一条边的有向无环图，必然存在一条路径，其起点是“入少出多”的点，终点是“出少入多”的点，所有中间点都是“入出相等”的点（只要不断的在图中找到并删去这条路径，直到图中无边为止）。
首先，由于图中无环，一定存在“入少出多”的点和“出少入多”的点。
然后，假设图中所有“入少出多”的点的后继（注意：后继和后代是不同的，一个点的后代包括这个点的所有后继、所有后继的后继、所有后继的后继的后继……）也都是“入少出多”的点，则图中所有“入少出多”的点构成了一个闭合子图，在这个闭合子图中，由于所有的点都是“入少出多”的，整个子图的入度之和必然大于出度之和，这是不可能的（有向图中的所有点入度之和必然等于所有点出度之和），故可得：图中必然存在至少一个“入少出多”的点，它有不是“入少出多”的后继。
这样，在这些拥有不是“入少出多”的后继的点中选择一个点i，将其作为路径的起点，在它的不是“入少出多”的后继中选出一个点j，若j是“出少入多”的点，则边<i, j>就是符合条件的一条路径，结束；若这样的j都是“入出相等”的点，则考虑j的后代：j的后继可能都是“入少出多”的，但j的后代中必然存在至少一个点j'不是“入少出多”的（否则j的所有后代也将构成全都是“入少出多”的闭合子图），这些j'中必然存在一个点的前趋i'是“入少出多”的，这是，需要舍弃原来的路径，将i'作为新路径的起点，j'作为新路径的第一个中间点，继续找；若j的后继不全是“入少出多”的，则若其中有“出少入多”的则路径已找到，若都是“入出相等”的，由于图中无环，将路径不断延伸，最终一定会找到合法路径。
为啥讲这道题呢，肯定跟本题有关系。
上面这个定理求出的解，肯定适用于本题。但是不一定是最优解，也就是有可能多走了若干次。
这个叫可行流，可以到对应一个建好的图中，如下所示：
设每个点i的入度减去出度为d[i], S为源点，T为汇点。
对于d[i] > 0的点i， 连边<i，T>
对于d[i] < 0的点i， 连边<S，i>
其它边连法与输入的边相同。
建好的这个图的最大流就是上边那个定理求出的解，假设为flow1。
然后有一个结论，求有下界的最小流的求法是：
首先要有可行流，然后倒向求解。
保持那个中间那些边方向不变，就是输入的那些边，
然后原来从源点连过来的点都连去汇点，原来连去汇点的都从源点连过去。
即对于d[i] < 0的点i， 连边<i，T>
对于d[i] >0的点i， 连边<S，i>
这其实啊 ，就是原来那个图，然后从T到S做最大流
假设这个求出的流量是flow2，则有下界的最小流的最优解是flow1-flow2
那么这是啥原理呢。
最开始的定理中说道对于一个至少有一条边的有向无环图，必然存在一条路径，其起点是“入少出多”的点，终点是“出少入多”的点，所有中间点都是“入出相等”的点
那么其实我们找的每条路径都是起点入少出多，差为1，终点，出少入多，也是差为1
反向建图求的是什么呢，就是在新图中起点出少入多的，差为1，终点，入少出多，也是差为1的路径
然后对于每找到这样的一个流的路径，可以将原始建图中的两条路径合并，然后新路径的中间点正好都是出入度相等的，两头出入度不同相差为1
我们通过画图来验证这个
例如此图，从上到下从左到右编号1->6
按照最开始那个定理求出的解有3个路径
1->3 2->3->4->5 4->6
然后你倒着建图 求出来了一条可以做衔接的路径 是3->4
1->3 4->6就被连接了
从而答案减去1
在画图的过程中，我们可以发现，对于每条这样的可以当做中间衔接的路径，一定可以合并原始建图中的两个路径。
然后本题的第一个问题就解决了
然后就是输出。
没有要求字典序。
具体的做法可以这样，在逆向的建图中，假如某条边走流量走了x ，则说明整个过程中该边被走了x+1次，
那么可以构造新图，同样的位置加入一条容量为x+1的边，
可以计算出这个新图的所有的d[i]，对于此图，就可以使用第一个定理来做了，必然得到最优解，
在具体实现中，可以通过dfs来寻找路径，以某点为开始时，能走就走，一直走到不能走为止，注意可能从某个点发出多个路径，
并且在走的时候需要注意的是，由于我们要删掉这条路径，会导致路径的开头和结尾的d发生变化，需要作出修改
代码参考了一下网上的一个人http://blog.csdn.net/auto_ac/article/details/9398657
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <set>
#include <vector>
#include <map>
#define MAXN 111
#define MAXM 55555
#define INF 1000000007
using namespace std;
struct EDGE {
int v, next;
int w;
}edge[MAXM];
int head[MAXN], e;
void init() {
memset(head, -1, sizeof(head));
e = 0;
}
void add(int u, int v, int w) {
edge[e].v = v;
edge[e].w = w;
edge[e].next = head[u];
head[u] = e++;
edge[e].v = u;
edge[e].w = 0;
edge[e].next = head[v];
head[v] = e++;
}
int n, nt;
int h[MAXN];
int gap[MAXN];
int src, des;
int dfs(int pos, int cost) {
if(pos == des) return cost;
int j, minh = n - 1;
int lv = cost, d;
for(j = head[pos]; j != -1; j = edge[j].next) {
int v = edge[j].v;
int w = edge[j].w;
if(w > 0) {
if(h[v] + 1 == h[pos]) {
if(lv < edge[j].w) d = lv;
else d = edge[j].w;
d = dfs(v, d);
edge[j].w -= d;
edge[j ^ 1].w += d;
lv -= d;
if(h[src] >= n) return cost - lv;
if(lv == 0) break;
}
if(h[v] < minh) minh = h[v];
}
}
if(lv == cost) {
--gap[h[pos]];
if(gap[h[pos]] == 0) h[src] = n;
h[pos] = minh + 1;
++gap[h[pos]];
}
return cost - lv;
}
int sap() {
int ret = 0;
memset(gap, 0, sizeof(gap));
memset(h, 0, sizeof(h));
gap[0] = n;
while(h[src] < n) ret += dfs(src, INF);
return ret;
}
int d[MAXN];
typedef pair<int, int> PII;
vector<PII> g[MAXN];
int ans[MAXN];
int cnt, flag;
void dfs(int u) {
int f = 0;
ans[cnt++] = u;
for(int i = 0; i < g[u].size(); i++) {
if(flag) return;
int v = g[u][i].first;
if(!g[u][i].second) continue;
f = 1;
--g[u][i].second;
dfs(v);
}
if(!f) d[u]--, flag = 1;
}
int main()
{
int u, v, t;
while(scanf("%d", &nt) != EOF) {
init();
memset(d, 0, sizeof(d));
for(int i = 1; i <= nt; i++) {
scanf("%d", &t);
while(t--) {
scanf("%d", &v);
d[i]--;
d[v]++;
add(i, v, INF);
}
}
src = nt + 1;
des = nt + 2;
n = nt + 2;
int res = 0;
for(int i = 1; i <= nt; i++) {
if(d[i] > 0) add(src, i, d[i]);
else if(d[i] < 0) add(i, des, -d[i]), res -= d[i];
}
printf("%d\n", res - sap());
for(int i = 1; i <= nt; i++) g[i].clear();
for(int i = 1; i <= nt; i++) {
for(int j = head[i]; j != -1; j = edge[j].next) {
if((j & 1) || edge[j].v > nt) continue;
g[i].push_back(make_pair(edge[j].v, edge[j ^ 1].w + 1));
d[i] -= edge[j ^ 1].w;
d[edge[j].v] += edge[j ^ 1].w;
}
}
for(int i = 1; i <= nt; i++) {
while(d[i] < 0) {
cnt = 0;
flag = 0;
d[i]++;
dfs(i);
for(int j = 0; j < cnt; j++) {
printf("%d", ans[j]);
if(j == cnt - 1) printf("\n");
else printf(" ");
}
}
}
}
return 0;
}