题意：给出若干个句子，每个句子包含多个单词。确定第一句是英文，第二句是法文。后面的句子两者都有可能。两个语种会有重复单词。
现在要找出一种分配方法（给每个句子指定其文种），使得既是英文也是法文的单词数量最少。
分析：网络流的最小割。
建图方法如下，每个句子一个点。每个单词一个点。句子向其所属的单词连双向无穷流量边。把第一个句子作为起点，第二句作为终点。
现在我们要割掉一些单词，使得起点无法到达终点。
图的意义是这样的。如果我们能找到一条从起点到达终点的通路，那么中间一定有一个过程是从一个英文句子跳到一个单词，然后跳到一个法文句子。这就说明该单词既是英文又是法文。
而如果找不到通路，把所有能到达的句子点归为英文，其余的归为法文。这样就成功地完成了划分任务，而没有同属于两个语言的单词。
所以，割掉单词使得图没有通路就是一种划分的充要条件。
割点的方法就是拆点，每个单词拆成两点，一个负责入边，一个负责出边。中间加一条流量为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 = 300; const int MAX_DIC = 1010; const int MAX_WORD_NUM = 20; const int MAX_NODE_NUM = (MAX_N * 10 + 2000) * 2 + 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 * 2]; 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, 0); head[v] = edge_cnt++; } void init() { edge_cnt = 0; memset(head, -1, sizeof(head)); } void q_init(int size) { front = 0; rear = 0; 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, 0, sizeof(vis)); memset(dep, -1, sizeof(dep)); q_init(MAX_NODE_NUM); q_push(s); vis[s] = true; dep[s] = 0; 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 > 0) { q_push(v); vis[v] = true; dep[v] = dep[u] + 1; } } } } int add_flow(int path[], int &path_n) { int min_edge = -1, delta = INF; for (int i = 0; i < path_n; ++i) { if (edge[path[i]].f < delta) { delta = edge[path[i]].f; min_edge = i; } } for (int i = 0; i < path_n; ++i) { edge[path[i]].f -= delta; edge[path[i] ^ 1].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 - 1]].v; return s; } int find_next(int start) { for (int e = cur[start]; ~e; e = edge[e].next) if (edge[e].f && dep[start] + 1 == dep[edge[e].v]) return e; return -1; } int dfs(int s, int t) { int ret = 0; int path_n = 0; 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 == -1) { if (path_n == 0) break; dep[x] = -1; --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 = 0; while (true) { bfs(s, t); if (dep[t] == -1) return ret; ret += dfs(s, t); } return -1; } int n; map<string, int> dictionary; vector<string> word[MAX_N]; void input() { dictionary.clear(); scanf("%d", &n); getchar(); for (int i = 0; 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() - 1; word[i].push_back(s); } } } int work() { init(); for (int i = 0; i < (int)dictionary.size(); i++) { int id1 = i * 2 + n; int id2 = id1 + 1; add_edge(id1, id2, 1); } for (int i = 0; i < n; i++) { for (int j = 0; j < (int)word[i].size(); j++) { int id = dictionary[word[i][j]]; int id1 = id * 2 + n; int id2 = id1 + 1; add_edge(i, id1, INF); add_edge(id2, i, INF); } } return dinic(0, 1); } int main() { int t; scanf("%d", &t); int case_num = 0; while (t--) { case_num++; printf("Case #%d: ", case_num); input(); printf("%d ", work()); bfs(0, 1); } return 0; }