题目是给你一个矩阵,1表示u可以到达v,0代表不可到达,问你至少需要多少条边组成的传递闭包符合这个矩阵。
我们可以求出强连通分量,然后在对每个强连通分量进行缩点,每个强连通分量的最少边的数量就是该强连通分量的结点数,再建立新图。对新图中的点用floyd算法,若图中用floyd算法能达到的,且在新图中为1的点,我们将它变为0,则答案就是每个强连通分量内的边数加上新图中为0的点的个数。
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> #include <queue> #include <stack> #include <vector> #include <ctype.h> #define INF 999999999 #define LL long long #define M 205 using namespace std; vector<int> G[M]; int dfn[M],low[M],sccno[M],scc_cnt; int indx; int num[M]; int d[M][M]; int TG[M][M]; stack<int> s; void Tarjan(int u) { indx++; dfn[u]=low[u]=indx; s.push(u); for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(!sccno[v]) { low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]) //缩点 { scc_cnt++; for(;;) { int x=s.top(); s.pop(); sccno[x]=scc_cnt; num[scc_cnt]++; //记录每个强连通分量的结点数 if(x==u) break; } } } void find_scc(int n) { indx=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(dfn,0,sizeof(dfn)); for(int i=0;i<n;i++) if(!dfn[i]) Tarjan(i); } int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) G[i].clear(); memset(num,0,sizeof(num)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { scanf("%d",&d[i][j]); if(i!=j && d[i][j]==1) G[i].push_back(j); } } find_scc(n); int ans=0; memset(TG,0,sizeof(TG)); for(int u=0;u<n;u++) //建立新图 { for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(sccno[u]!=sccno[v] && d[u][v]==1) TG[sccno[u]][sccno[v]]=1; } } for(int k=1;k<=scc_cnt;k++) //floyd算法 { for(int i=1;i<=scc_cnt;i++) { for(int j=1;j<=scc_cnt;j++) { if(TG[i][j]==1 && TG[i][k]==1 && TG[k][j]==1) TG[i][j]=0; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(TG[i][j]==1) ans++; } } for(int i=1;i<=scc_cnt;i++) { if(num[i]>1) ans+=num[i]; } printf("%d\n",ans); } return 0; }