uva 1440 & uvalive 4597

题意：

DAG的最小路径覆盖，一条边可以被重复覆盖多次，但是一次只能沿着DAG的方向覆盖一条链，问最少覆盖次数。

思路：

看了半天没有思路，所以去搜索了题解，然后发现是有源汇上下界的最小流，这个东西依赖于有源汇上下界的可行流，然后又依赖于无源汇上下界可行流，所以就都去学了一下，写一个简单的总结与建模方法。

无源汇上下界可行流：

首先强行指定每条边的流为下界，然后会很大概率出现流量不平衡的现象，那么现在需要让流量平衡，就需要补流与分流。

强行指定之后，设流入每个点的流量为\(in_i\)，流出每个点的流量为\(out_i\)，那么就有3种情况：

\(in_i = out_i\)，此时无需做任何事情；
\(in_i > out_i\)，流入的流量比流出的流量多，那么需要从附加源点\(SS\)引入\(in_i - out_i\)的流，即加边\(adde(SS,i,in[i]-out[i])\)；
\(in_i < out_i\)，流出的流量比流入的流量多，那么需要从点分流\(out_i - in_i\)到附加汇点\(TT\)，即加边\(adde(i,TT,out[i]-in[i])\).

此时，只是处理完了需要流量平衡的地方，现在还需要对边的流量的上界进行限制，由于已经强行指定了边的下界，所以每一条边的上界都是原来的上界减去下界，按照这个限制对图加边即可。

最后，求\(SS\)到\(TT\)的最大流，如果满流，则说明这个图有可行流，并且每一条边的流为附加流加上指定的下界。

有源汇上下界可行流：

转化为无源汇上下界可行流，只需要加边\(adde(T,S,inf)\)，如此就可以保证源点和汇点也流量平衡（无源汇可行流的基础就是流量平衡）。

加边之后，按照无源汇可行流求解即可，并且\(T\)到\(S\)的反向边的流量就是原图的一个可行流。

有源汇上下界最大流：

转化为有源汇上下界可行流，在这个残量网络上求从\(S\)到\(T\)的最大流，加上之前求的可行流即是本图的最大流。

有源汇上下界最小流：

转化为可行流问题，但是稍微有不同。

首先不连边\(adde(T,S,inf)\)，然后求\(SS\)到\(TT\)的最大流；

之后连边\(adde(T,S,inf)\)，再次求\(SS\)到\(TT\)的最大流，这个最大流就是我们所求的最小流，原理不太懂，参考。

题目思路：

从源点到每个点连边，下界为0，上界为inf，表示这个点可以放下任意数量的人；

从每个点到汇点连边，下界为0，上界为inf，表示任意数量的人在这个点停止；

题目中给出的边，下界为1，上界为inf，表示每条边至少被覆盖一次。

然后求有源汇上下界最小流即可。

然后是找路径，dfs找到return即可。

但是得从S开始找，不要从某一个点开始找。假设从S到1的流量为3，但是1流出的总流量为5，从1开始dfs，就会出现某个后面的点无法找到路径的情况。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int inf = 0x3f3f3f3f;

const int N = 2e2 + 5;

vector<int> g[N];

vector<vector<int> > anc;

vector<int> tp;

int mp[N][N];

int in[N],out[N];

int dis[N],cur[N];

int S,T,SS,TT;

int st,en;

struct edge

{

	int u,v,cap,org;

	edge(int u,int v,int cap,int org):u(u),v(v),cap(cap),org(org){}

};

vector<edge> es;

vector<int> G[N];

void adde(int u,int v,int cap)

{

	es.push_back(edge(u,v,cap,cap));

	es.push_back(edge(v,u,0,0));

	int sz = es.size();

	G[u].push_back(sz-2);

	G[v].push_back(sz-1);

}

bool bfs()

{

	memset(dis,inf,sizeof dis);

	dis[st] = 0;

	queue<int> q;

	q.push(st);

	while (!q.empty())

	{

		int u = q.front();

		q.pop();

		for (int i = 0;i < G[u].size();i++)

		{

			edge &e = es[G[u][i]];

			int v = e.v;

			if (dis[v] >= inf && e.cap > 0)

			{

				dis[v] = dis[u] + 1;

				q.push(v);

			}

		}

	}

	return dis[en] < inf;

}

int dfs(int u,int flow)

{

	if (u == en) return flow;

	for (int i = cur[u];i < G[u].size();i++)

	{

		cur[u] = i;

		edge &e = es[G[u][i]];

		int v = e.v;

		if (dis[v] == dis[u] + 1 && e.cap > 0)

		{

			int tmp = dfs(v,min(flow,e.cap));

			if (tmp)

			{

				e.cap -= tmp;

				es[G[u][i]^1].cap += tmp;

				return tmp;

			}

		}

	}

	return 0;

}

int dinic()

{

	int ans = 0;

	while (bfs())

	{

		memset(cur,0,sizeof cur);

		int tmp;

		while (tmp = dfs(st,inf)) ans += tmp;

	}

	return ans;

}

void fin(int u)

{

	tp.push_back(u);

	for (int i = 0;i < g[u].size();i++)

	{

		int v = g[u][i];

		if (mp[u][v])

		{

			mp[u][v]--;

			fin(v);

			return;

		}

	}

}

int main()

{

	int n;

	while (~scanf("%d",&n))

	{

		for (int i = 0;i < N;i++)

		{

			g[i].clear();

			G[i].clear();

		}

		es.clear();

		memset(in,0,sizeof in);

		memset(out,0,sizeof out);

		memset(mp,0,sizeof mp);

		anc.clear();

		for (int i = 1;i <= n;i++)

		{

			int m;

			scanf("%d",&m);

			for (int j = 0;j < m;j++)

			{

				int x;

				scanf("%d",&x);

				g[i].push_back(x);

				mp[i][x]++;

			}

		}

		for (int i = 1;i <= n;i++)

		{

			for (int j = 0;j < g[i].size();j++)

			{

				int x = g[i][j];

				out[i]++;

				in[x]++;

			}

		}

		S = 0;T = n + 1;

		SS = n + 2;TT = n + 3;

		for (int i = 1;i <= n;i++)

		{

			for (int j = 0;j < g[i].size();j++)

			{

				int x = g[i][j];

				adde(i,x,inf);

			}

		}

		int sum = 0;

		for (int i = 1;i <= n;i++)

		{

			adde(S,i,inf);

			adde(i,T,inf);

		}

		//adde(T,S,inf);

		int cnt = 0;

		for (int i = 1;i <= n;i++)

		{

			if (in[i] > out[i])

			{

				cnt++;

				adde(SS,i,in[i] - out[i]);

				sum += in[i] - out[i];

			}

			else if (in[i] < out[i])

			{

				cnt++;

				adde(i,TT,out[i] - in[i]);

			}

		}

		//puts("GG");

		st = SS;en = TT;

		dinic();

		adde(T,S,inf);

		//printf("%d %d\n",sum,ans);

		//if (ans == sum) puts("Yes");

		//else puts("No");

		int ans = dinic();

		printf("%d\n",ans);

		//printf("%d\n",dec);

		for (int i = 1;i <= n;i++)

		{

			for (int j = 0;j < G[i].size();j++)

			{

				edge e = es[G[i][j]];

				if (e.v == S || e.v == T || e.org == 0 || e.v == SS || e.v == TT) continue;

				mp[i][e.v] += e.org - e.cap;

			}

		}

		for (int i = 0;i < G[S].size();i++)

		{

			edge e = es[G[S][i]];

			int v = e.v;

			if (v >= 1 && v <= n)

			{

				int c = e.org - e.cap;

				while (c)

				{

					tp.clear();

					fin(v);

					anc.push_back(tp);

					c--;

				}

			}

		}

		for (int i = 0;i < anc.size();i++)

		{

			tp = anc[i];

			int sz = tp.size();

			for (int j = 0;j < sz;j++)

			{

				printf("%d%c",tp[j],j == sz - 1 ? '\n' : ' ');

			}

		}

	}

	return 0;

}

/*

8

1 3

1 7

2 4 5

1 8

1 8

0

2 6 5

0

*/

巴特西