题意很简单：

给出一张有向图，每次你可以从图中的任意一点出发，经过若干条边后停止，然后问你最少走几次可以将图中的每条边都走过至少一次，并且要输出方案

这个转化为网络流的话，就相当于 求一个最小流，并且存在下界，即每条边至少走一次

这让我联想到很久之前的一道题，也是有向图，问走多少条路径可以将整个图中的每条边都走过，但是跟本题不同的是，那题是不允许重复走边的。

那道题目的解是这样的：

对于图中的每个点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 = http://www.mamicode.com/nt + 1;>

UVA1440  有下界的最小流