题意：给出若干个句子，每个句子包含多个单词。确定第一句是英文，第二句是法文。后面的句子两者都有可能。两个语种会有重复单词。
现在要找出一种分配方法（给每个句子指定其文种），使得既是英文也是法文的单词数量最少。
分析：网络流的最小割。
建图方法如下，每个句子一个点。每个单词一个点。句子向其所属的单词连双向无穷流量边。把第一个句子作为起点，第二句作为终点。
现在我们要割掉一些单词，使得起点无法到达终点。
图的意义是这样的。如果我们能找到一条从起点到达终点的通路，那么中间一定有一个过程是从一个英文句子跳到一个单词，然后跳到一个法文句子。这就说明该单词既是英文又是法文。
而如果找不到通路，把所有能到达的句子点归为英文，其余的归为法文。这样就成功地完成了划分任务，而没有同属于两个语言的单词。
所以，割掉单词使得图没有通路就是一种划分的充要条件。
割点的方法就是拆点，每个单词拆成两点，一个负责入边，一个负责出边。中间加一条流量为1的边。
本题还有一个难点就是输入，每个句子要自己根据空格划分成单词。
stringstream可以将字符串作为输入流，从中读入内容。用stringstream sin(inputstring); 之后读入方法与cin一样。需要包含sstream头文件。
char*转化成string可以直接用等号赋值。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <sstream>
using namespace std; #define D(x) const int MAX_N = ;
const int MAX_DIC = ;
const int MAX_WORD_NUM = ; const int MAX_NODE_NUM = (MAX_N * + ) * + MAX_N;
const int MAX_EDGE_NUM = (int)(1e6);
#define INF 0x3f3f3f3f struct Edge
{
int next, v, f;
Edge()
{}
Edge(int next, int v, int f):next(next), v(v), f(f)
{}
} edge[MAX_EDGE_NUM * ]; int head[MAX_NODE_NUM];
int q[MAX_NODE_NUM];
bool vis[MAX_NODE_NUM];
int cur[MAX_NODE_NUM];
int dep[MAX_NODE_NUM];
int edge_cnt;
int path[MAX_NODE_NUM];
int front, rear, q_size; void add_edge(int u, int v, int f)
{
edge[edge_cnt] = Edge(head[u], v, f);
head[u] = edge_cnt++;
edge[edge_cnt] = Edge(head[v], u, );
head[v] = edge_cnt++;
} void init()
{
edge_cnt = ;
memset(head, -, sizeof(head));
} void q_init(int size)
{
front = ;
rear = ;
q_size = size;
} void q_push(int a)
{
q[rear++] = a;
rear %= q_size;
} int q_pop()
{
int ret = q[front++];
front %= q_size;
return ret;
} void bfs(int s, int t)
{
memset(vis, , sizeof(vis));
memset(dep, -, sizeof(dep));
q_init(MAX_NODE_NUM);
q_push(s);
vis[s] = true;
dep[s] = ;
while (front != rear && !vis[t])
{
int u = q_pop();
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].v;
if (!vis[v] && edge[i].f > )
{
q_push(v);
vis[v] = true;
dep[v] = dep[u] + ;
}
}
}
} int add_flow(int path[], int &path_n)
{
int min_edge = -, delta = INF;
for (int i = ; i < path_n; ++i)
{
if (edge[path[i]].f < delta)
{
delta = edge[path[i]].f;
min_edge = i;
}
}
for (int i = ; i < path_n; ++i)
{
edge[path[i]].f -= delta;
edge[path[i] ^ ].f += delta;
}
path_n = min_edge;
return delta;
} int last_node(int path[], int path_n, int s)
{
if (path_n)
return edge[path[path_n - ]].v;
return s;
} int find_next(int start)
{
for (int e = cur[start]; ~e; e = edge[e].next)
if (edge[e].f && dep[start] + == dep[edge[e].v])
return e;
return -;
} int dfs(int s, int t)
{
int ret = ;
int path_n = ;
int x = s;
memcpy(cur, head, sizeof(cur));
while (true)
{
if (x == t)
{
ret += add_flow(path, path_n);
x = last_node(path, path_n, s);
}
int next_edge = find_next(x);
cur[x] = next_edge;
if (next_edge == -)
{
if (path_n == )
break;
dep[x] = -;
--path_n;
x = last_node(path, path_n, s);
continue;
}
path[path_n++] = next_edge;
x = edge[next_edge].v;
}
return ret;
} int dinic(int s, int t)
{
int ret = ;
while (true)
{
bfs(s, t);
if (dep[t] == -)
return ret;
ret += dfs(s, t);
}
return -;
} int n;
map<string, int> dictionary;
vector<string> word[MAX_N]; void input()
{
dictionary.clear();
scanf("%d", &n);
getchar();
for (int i = ; i < n; i++)
{
word[i].clear();
char st[MAX_DIC * MAX_WORD_NUM];
fgets(st, MAX_DIC * MAX_WORD_NUM, stdin);
string s = st;
stringstream sin(s);
while (sin >> s)
{
if (dictionary.find(s) == dictionary.end())
dictionary[s] = dictionary.size() - ;
word[i].push_back(s);
}
}
} int work()
{
init();
for (int i = ; i < (int)dictionary.size(); i++)
{
int id1 = i * + n;
int id2 = id1 + ;
add_edge(id1, id2, );
}
for (int i = ; i < n; i++)
{
for (int j = ; j < (int)word[i].size(); j++)
{
int id = dictionary[word[i][j]];
int id1 = id * + n;
int id2 = id1 + ;
add_edge(i, id1, INF);
add_edge(id2, i, INF);
}
}
return dinic(, );
} int main()
{
int t;
scanf("%d", &t);
int case_num = ;
while (t--)
{
case_num++;
printf("Case #%d: ", case_num);
input();
printf("%d\n", work());
bfs(, );
}
return ;
}