题意：给你一个传递闭包的矩阵，mp[u][v] = 1表示u可以到达v，为0代表不可到达，问你至少需要多少条边组成的传递闭包符合这个矩阵给出的关系
分析：考虑一个强连通分量，如果这个分量有n个节点，那么至少只需要n条边皆可以满足传递闭包（因为此时形成环就可），所以求出所有的强连通分量，将他们缩成一个个的点，并记录该强连通分量有多少个节点，然后建立新图，在运行一遍floyd算法，去除所有满足 tG[i][k]&&tG[k][j]&&tG[i][j]的边(i,j)，然后统计还剩多少边，再加上每个强连通分量的节点数。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define N 207 vector<int> G[N];
int mp[][],tG[][];
stack<int> stk;
int instk[N],cnt,Time,n;
int low[N],dfn[N],bel[N],num[N]; void tarjan(int u)
{
low[u] = dfn[u] = ++Time;
stk.push(u);
instk[u] = ;
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(instk[v])
low[u] = min(low[u],dfn[v]);
}
if(low[u] == dfn[u])
{
cnt++;
int v;
do
{
v = stk.top();
stk.pop();
instk[v] = ;
bel[v] = cnt;
num[cnt]++;
}while(u != v);
}
} void Tarjan()
{
memset(bel,,sizeof(bel));
memset(instk,,sizeof(instk));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(num,,sizeof(num));
Time = cnt = ;
while(!stk.empty())
stk.pop();
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i);
} void Build()
{
int i,j;
memset(tG,,sizeof(tG));
for(i=;i<=n;i++)
{
for(j=;j<G[i].size();j++)
{
int v = G[i][j];
if(bel[i] != bel[v] && mp[i][v])
tG[bel[i]][bel[v]] = ;
}
}
} int main()
{
int i,j,k,u,v;
while(scanf("%d",&n)!=EOF)
{
for(i=;i<=n;i++)
G[i].clear();
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
scanf("%d",&mp[i][j]);
if(i == j || !mp[i][j])
continue;
G[i].push_back(j);
}
}
Tarjan();
Build();
for(k=;k<=cnt;k++)
{
for(i=;i<=cnt;i++)
{
for(j=;j<=cnt;j++)
{
if(tG[i][j] && tG[i][k] && tG[k][j])
tG[i][j] = ;
}
}
}
int res = ;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(tG[i][j])
res++;
for(i=;i<=cnt;i++)
{
if(num[i] > )
res += num[i];
}
printf("%d\n",res);
}
return ;
}