学二分图那么久，真是白学了，妥妥的最小路径覆盖都木有看出来。弱爆了。
链接：
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2655
给你一个图，最多有100个点，一开始有很多（不知道多少）个机器人在编号为1的点上，现在机器人开始移动，每当有一个机器人进入一个新点的时候，就会报出新点的编号。现在我们得到了一个长度不超过200的报号序列，想知道一开始最多和最少有几个机器人。注意所谓的新点即“与报号机器人之前所在的点不同”，所以每当一个机器人移动到下一个点时就会发生报号，并且机器人可以往复运动。
对于最多有多少个机器人，可以有一个猜想，即如果所有的报号均为不同的机器人报出的，可能吗？如果不可能，什么样的情况不可能？即，不和1点直接相连的点的编号显然不可能是由新出现的机器人报出的。所以，最大的机器人数量即为报号序列中与1号点相连的点的编号出现的次数。
对于最少有多少个机器人，那么裸的最小路径覆盖模型啊。我个蒟蒻。
模型转化：我们怎样才能使机器人最少呢？即是让尽量少的机器人去报这个报号序列：如果把报号序列抽象成一个有向新图的话，就用尽量的少的路径来覆盖这个新图。最小路径覆盖模型即得。
建图方式：M^2建图，对于序列中的每个点枚举它之后的点列，看在原图中两点是否相连，如果相连，则在新图中连一条有向边。
然后匈牙利，再然后就M-二分图最大匹配即为答案。
（蒻弼，你不打错下标能死啊？你认真点能死啊！）
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 205
int mac[maxn];
bool vis[maxn],graph[maxn][maxn],old[maxn][maxn];
int n,m;
int input[maxn];
bool find(int x)
{
for(int i = 1;i <= m;i++)
if(graph[x][i] && !vis[i])
{
vis[i] = true;
if(!mac[i] || find(mac[i]))
{
mac[i] = x;
return true;
}
}
return false;
}
int main()
{
while(scanf("%d%d",&n,&m) == 2 && (n || m))
{
memset(old,0,sizeof(old));
memset(graph,0,sizeof(graph));
memset(mac,0,sizeof(mac));
for(int i = 1;i <= n;i++)
{
int c;
scanf("%d",&c);
for(int j = 1;j <= c;j++)
{
int a;
scanf("%d",&a);
old[i][a] = true;
}
}
int ans2 = 0;
for(int i = 1;i <= m;i++)
{
scanf("%d",&input[i]);
if(old[1][input[i]])
ans2++;
}
for(int i = 1;i <= m;i++)
for(int j = i + 1;j <= m;j++)
if(old[input[i]][input[j]])
graph[i][j] = true;
int ans1 = m;
for(int i = 1;i <= m;i++)
{
fill(vis,vis + m + 1,0);
if(find(i))
ans1--;
}
printf("%d %d\n",ans1,ans2);
}
}
Down