题意：给出一个有向图的传递背包，求原图最少有多少边。
思路：用强连通缩点(在一个强连通里面，剩下一个简单环就可以了，n=1特殊处理)，再用floyd简化缩点后的图(就是a->b,b->c,a->c,就可以吧a->c去掉)，最后统计。
#include<stdio.h>
#include<string.h>
#include<queue>
#define min(a,b) (a<b?a:b)
#define maxn 300
#define maxe 50000
using namespace std;
int dfn[maxn],low[maxn],m[maxn][maxn],mi[maxn][maxn];
int head[maxn],stack[maxn],belong[maxn];
int come[maxn],cou[maxn];
int times,top,scc,EN,ans,ENN;
struct ED
{
int v,next;
}edge[maxe],ed[maxe];
void addedge(int u,int v)
{
edge[EN].v=v;
edge[EN].next=head[u];
head[u]=EN++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++times;
stack[++top]=u;
int v;
for(int i=head[u];~i;i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!belong[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
scc++;
do
{
v=stack[top--];
belong[v]=scc;
cou[scc]++;
}while(v!=u);
if(cou[scc]==1)
cou[scc]=0;
}
}
void floy(int N,int mat[][maxn],int mi[][maxn])
{
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
mi[i][j]=mat[i][j];
for(int i=1;i<=N;i++)
mi[i][i]=0;
for(int k=1;k<=N;k++)
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(mi[i][k]&&mi[k][j])
mi[i][j]=0;
return;
}
int main()
{
int N,c;
while(scanf("%d",&N)!=EOF)
{
top=EN=times=scc=ans=0;
memset(head,-1,sizeof(head));
memset(belong,0,sizeof(belong));
memset(dfn,0,sizeof(dfn));
memset(cou,0,sizeof(cou));
memset(m,0,sizeof(m));
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
scanf("%d",&c);
if(c&&i!=j)
addedge(i,j);
}
for(int i=0;i<N;i++)
if(!dfn[i])
tarjan(i);
for(int u=0;u<N;u++)
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].v;
if(belong[u]!=belong[v])
m[belong[u]][belong[v]]=1;
}
for(int i=1;i<=scc;i++)
ans+=cou[i];
floy(scc,m,mi);
for(int i=1;i<=scc;i++)
for(int j=1;j<=scc;j++)
if(mi[i][j])
ans++;
printf("%d\n",ans);
}
return 0;
}