题目大意是给你一个1000个点10000条边的有向图，让你求出与原图等价的传递闭包的最少边和最多边。
解法：
最多边好求，就dfs一下（floyd的邻接表版）算出闭包，统计一下邻接矩阵中1的个数再减去自环即为答案。
最少边稍微复杂一点：
首先图的强联通分量内的边都是必要边，而两两分量之间去掉多重边即可。
关键点是多重边的去除：强联通分量缩点以后，在新图上从每点开始用bfs或者dp做最长路（因为如果某条重复边跨越了某条路径的话，那么对于路径起点来说，路径终点的距离一定不是由这条重复边松弛的），对于每个点，存在几个距离为1的点计数器就加几，然后再加上每个强联通分量之中的边数即可（对于点数大于1的强联通分量，边数=点数）。
纠结，知道怎么捉，不知怎么说，我太弱了。对于纯图论的问题的想法还是太弱了。
附代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#include <queue>
#define maxn 1005
#define maxm 10005
bool map[maxn][maxn];
int n,m,tot,newtot;
int st[maxn];
int sc[maxn],newst[maxn],pre[maxn],low[maxn],s[maxn],color[maxn];
bool vis[maxn];
bool viscolor[maxn],colorvis[maxn];
int N,cnt0,cnt1;
int d[maxn];
int mmm,MMM;
struct edge
{
int p,next;
edge(){}
edge(int a,int b):p(a),next(b){}
}e[maxm],newe[maxm];
void init()
{
newtot = 0;
tot = cnt0 = cnt1 = N = 0;
fill(newst,newst + n + 1,-1);
fill(st,st + n + 1,-1);
fill(vis,vis + n + 1,0);
fill(color,color + n + 1,0);
fill(pre,pre + n + 1,-1);
fill(low,low + n + 1,-1);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
{
if(i == j)
map[i][j] = 1;
else
map[i][j] = 0;
}
}
void add(int p,int q)
{
e[tot] = edge(q,st[p]);
st[p] = tot++;
}
void newadd(int p,int q)
{
newe[newtot] = edge(q,newst[p]);
newst[p] = newtot++;
}
void dfs(int u,int v)
{
map[u][v] = 1;
for(int k = st[v];~k;k = e[k].next)
if(map[u][e[k].p] == 0)
dfs(u,e[k].p);
}
void scc(int now)
{
int v,mm;
mm = low[now] = pre[now] = cnt0++;
s[N++] = now;
for(int k = st[now];~k;k = e[k].next)
{
if(pre[e[k].p] == -1)
scc(e[k].p);
if(low[e[k].p] < mm)
mm = low[e[k].p];
}
if(mm < low[now])
{
low[now] = mm;
return ;
}
do
{
sc[(v = s[--N])] = cnt1;
low[v] = n;
}while(s[N] != now);
cnt1++;
}
void bfs(int x)
{
fill(d,d + cnt1 + 1,0);
queue <int> Q;
Q.push(x);
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int k = newst[now];~k;k = newe[k].next)
{
if(d[newe[k].p] < d[now] + 1)
{
d[newe[k].p] = d[now] + 1;
Q.push(newe[k].p);
}
}
}
for(int i = 0;i < cnt1;i++)
if(d[i] == 1)
mmm++;
}
void gao()
{
scanf("%d %d",&n,&m);
init();
for(int i = 0;i < m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
}
for(int i = 1;i <= n;i++)
dfs(i,i);
mmm = 0,MMM = 0;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
if(map[i][j])
MMM++;
MMM -= n;
for(int i = 1;i <= n;i++)
if(pre[i] == -1)
scc(i);
for(int i = 1;i <= n;i++)
{
color[sc[i]]++;
for(int k = st[i];~k;k = e[k].next)
if(sc[i] != sc[e[k].p])
newadd(sc[i],sc[e[k].p]);
}
for(int i = 0;i < cnt1;i++)
bfs(i);
for(int i = 0;i < n;i++)
if(color[i] > 1)
mmm += color[i];
printf("%d %d\n",mmm,MMM);
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 1;i <= t;i++)
{
printf("Case #%d: ",i);
gao();
}
}
Down