湖北省网站备案,360建筑网简历电话怎么修改,阿里云 有企业 网站吗,家用机能否做网站服务器https://vjudge.net/problem/UVA-11324 题意#xff1a;给一张有向图G#xff0c;求一个结点数最大的结点集#xff0c;使得该结点集中任意两个结点u和v满足#xff0c;要么u可以到达v#xff0c;要么v可以达到u。 思路#xff1a; 找到SCC后进行缩点建图#xff0c;每个…https://vjudge.net/problem/UVA-11324 题意给一张有向图G求一个结点数最大的结点集使得该结点集中任意两个结点u和v满足要么u可以到达v要么v可以达到u。 思路 找到SCC后进行缩点建图每个点的权值则为其连通分量的点数这样就是找DAG上一条最大路径DP解决。 1 #includeiostream2 #includealgorithm3 #includecstring4 #includecstdio5 #includevector6 #includestack7 #includequeue8 #includecmath9 using namespace std;10 11 const int maxn10005;12 13 int n,m;14 15 vectorint G[maxn];16 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;17 int num[maxn];18 int map[maxn][maxn];19 int d[maxn];20 stackint S;21 22 void dfs(int u)23 {24 pre[u]lowlink[u]dfs_clock;25 S.push(u);26 for(int i0;iG[u].size();i)27 {28 int vG[u][i];29 if(!pre[v])30 {31 dfs(v);32 lowlink[u]min(lowlink[u],lowlink[v]);33 }34 else if(!sccno[v])35 {36 lowlink[u]min(lowlink[u],pre[v]);37 }38 }39 if(lowlink[u]pre[u])40 {41 scc_cnt;42 for(;;)43 {44 int xS.top(); S.pop();45 sccno[x]scc_cnt;46 if(xu) break;47 }48 }49 }50 51 void find_scc()52 {53 dfs_clockscc_cnt0;54 memset(sccno,0,sizeof(sccno));55 memset(pre,0,sizeof(pre));56 for(int i0;in;i)57 if(!pre[i]) dfs(i);58 }59 60 int dp(int u)61 {62 int ansd[u];63 if(ans!-1) return ans;64 ansnum[u];65 for(int i1;iscc_cnt;i)66 {67 if(i!u map[u][i]) ansmax(ans,num[u]dp(i));68 }69 return ans;70 }71 72 int main()73 {74 //freopen(D:\\input.txt,r,stdin);75 int T;76 scanf(%d,T);77 while(T--)78 {79 scanf(%d%d,n,m);80 for(int i0;in;i) G[i].clear();81 while(m--)82 {83 int u,v;84 scanf(%d%d,u,v);85 u--; v--;86 G[u].push_back(v);87 }88 find_scc();89 memset(num,0,sizeof(num));90 memset(map,0,sizeof(map));91 for(int i0;in;i)92 num[sccno[i]];93 for(int u0;un;u)94 {95 for(int i0;iG[u].size();i)96 {97 int xsccno[u];98 int ysccno[G[u][i]];99 map[x][y]1;
100 }
101 }
102 int ans0;
103 memset(d,-1,sizeof(d));
104 for(int i1;iscc_cnt;i)
105 ansmax(ans,dp(i));
106 printf(%d\n,ans);
107 }
108 return 0;
109 } 转载于:https://www.cnblogs.com/zyb993963526/p/6798234.html
