The Maximum Unreachable Node Set
In this problem, we would like to talk about unreachable sets of a directed acyclic graph G = (V,E). In mathematics a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is a graph such that there is no way to start at any node and follow a consistently-directed sequence of edges in E that eventually loops back to the beginning again.
A node set denoted by $V_{U}R⊂V$ containing several nodes is known as an unreachable node set of G if, for each two different nodes u and v in $V_{UR}$, there is no way to start at u and follow a consistently-directed sequence of edges in E that finally archives the node v. You are asked in this problem to calculate the size of the maximum unreachable node set of a given graph G.
Input
The input contains several test cases and the first line contains an integer T(1≤T≤500) which is the number of test cases.
For each case, the first line contains two integers nn(1≤n≤100) and m(0≤m≤n(n−1)/2) indicating the number of nodes and the number of edges in the graph G. Each of the following mm lines describes a directed edge with two integers u and v (1≤u,v≤n and u≠v) indicating an edge from the u-th node to the v-th node. All edges provided in this case are distinct.
We guarantee that all directed graphs given in input are DAGs and the sum of m in input is smaller than 500000.
Output
For each test case, output an integer in a line which is the size of the maximum unreachable node set of GG.
样例输入
3
4 4
1 2
1 3
2 4
3 4
4 3
1 2
2 3
3 4
6 5
1 2
4 2
6 2
2 3
2 5样例输出
2
1
3链接
题意
给定一个有向无环图，求最大不可到达的点集（对于集合中任意两点u、v，不能从点u出发到达点v）。
题解
使用Floyd求传递闭包得到可达矩阵，然后跑一遍二分图最大匹配，答案就是顶点数减去二分图最大匹配。其实就是顶点数减去最小路径覆盖，有点最大独立集的感觉。
二分图：任意一张图，若能将所有顶点分为两个互斥的集合，每个集合内的点两两互不相连，则可看做二分图（二部图）根据题意，计算图的可达性矩阵，用此矩阵作为二分图，就可用匈牙利算法算出二分图的最大匹配数res，注意res是匹配成功的有向边的数目，所以最多有res个点可以被到达（或者说有res个点可以出去）不能被到达的点，就可以抠出来，作为符合本题的那个点集合。
另一种理解，匹配完边之后，有n-res个点没有被到达，也就是可以有从这n-res个点起始的n-res条路（平行的），从这n-res条路上各取一点，必定互不相连，故答案为n-res。
——传送门
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
int G[maxn][maxn];
int n, m;
int linker[maxn];
bool used[maxn];
void floyd()
{
for (int k = 1; k <= n; ++k)
{
for (int i = 1; i <= n; ++i)
{
if (G[i][k])
{
for (int j = 1; j <= n; ++j)
if (G[k][j])
G[i][j] = 1;
}
}
}
}
//void floyd()
//{
// for (int k = 1; k <= n; ++k)
// for (int i = 1; i <= n; ++i)
// for (int j = 1; j <= n; ++j)
// G[i][j] |= G[i][k] & G[k][j];
//}
bool dfs(int u)
{
for (int i = 1; i <= n; ++i)
{
if (G[u][i] && !used[i])
{
used[i] = true;
if (linker[i] == -1 || dfs(linker[i]))
{
linker[i] = u;
return true;
}
}
}
return false;
}
int solve()
{
int res = 0;
memset(linker, -1, sizeof(linker));
for (int i = 1; i <= n; ++i)
{
memset(used, 0, sizeof(used));
if (dfs(i))
++res;
}
return res;
}
int main()
{
int T, u, v;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
memset(G, 0, sizeof(G));
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
G[u][v] = 1;
}
floyd();
int ans = n - solve();
printf("%d\n", ans);
}
return 0;
}Vjudge上交UVALive一直WA，找网上的代码也是WA，后面看了一下提交记录，貌似没有过的，玄学，可以去计蒜客或者中国石油大学OJ上交。
The end.
2018-08-24 星期五