傳送門：http://acm.hdu.edu.cn/showproblem.php?pid=4635

解題思路：

題目大意是你能最多能添加多少邊，使的這個(gè)圖不是強(qiáng)連通圖。其臨界條件是差一條邊成強(qiáng)連通圖。

可以把圖分成兩個(gè)強(qiáng)連通圖，左邊的一個(gè)強(qiáng)連通分量點(diǎn)個(gè)數(shù)為y，右邊一個(gè)強(qiáng)連通分量的個(gè)數(shù)為x。

然后x的所有點(diǎn)都與y的所有點(diǎn)都有x->y連線,沒(méi)有y-x的連線。這就是最終答案。

x+y=n

x×（x-1）+y×（y-1）+x×y-m

化簡(jiǎn)的 n×n-x×y-n-m，很明顯只有|x-y|的絕對(duì)值越大，最終結(jié)果就越大。

最后我們用Tarjan算法，進(jìn)行縮點(diǎn)后可能形成現(xiàn)在這樣的圖

很明顯只有入度，或出度為零的點(diǎn)才能選做x，或y。

實(shí)現(xiàn)代碼：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int MAXN=100010; 8 9 struct Edge{ 10 int to,next; 11 }edges[MAXN]; 12 13 int head[MAXN],tot; 14 15 void init(){ 16 memset(head,-1,sizeof(head)); 17 tot=0; 18 } 19 20 void addEdge(int u,int v){ 21 edges[tot].to=v; 22 edges[tot].next=head[u]; 23 head[u]=tot++; 24 } 25 26 int DFN[MAXN],LOW[MAXN],Stack[MAXN],NUM[MAXN],Belong[MAXN]; 27 bool Instack[MAXN]; 28 int scc,Index,top; 29 30 void Tarjan(int u){ 31 DFN[u]=LOW[u]=++Index; 32 Stack[top++]=u; 33 Instack[u]=true; 34 35 int v; 36 for(int i=head[u];i!=-1;i=edges[i].next){ 37 v=edges[i].to; 38 39 if(!DFN[v]){ 40 Tarjan(v); 41 if(LOW[u]>LOW[v]) 42 LOW[u]=LOW[v]; 43 }else if(Instack[v]&&LOW[u]>DFN[v]) LOW[u]=DFN[v]; 44 } 45 46 if(LOW[u]==DFN[u]){ 47 scc++; 48 do{ 49 v=Stack[--top]; 50 NUM[scc]++; 51 Instack[v]=false; 52 Belong[v]=scc; 53 }while(v!=u); 54 } 55 } 56 57 int in[MAXN],out[MAXN]; 58 void solve(long long n,long long m){ 59 memset(DFN,0,sizeof(DFN)); 60 memset(NUM,0,sizeof(NUM)); 61 memset(Instack,0,sizeof(Instack)); 62 top=Index=scc=0; 63 64 for(int i=1;i<=n;i++) 65 if(!DFN[i]) 66 Tarjan(i); 67 68 if(scc==1){ 69 cout<<-1<<endl; 70 return; 71 } 72 73 memset(in,0,sizeof(in)); 74 memset(out,0,sizeof(out)); 75 76 for(int i=1;i<=n;i++) 77 for(int j=head[i];j!=-1;j=edges[j].next){ 78 int v=edges[j].to; 79 if(Belong[i]!=Belong[v]){ 80 out[Belong[i]]++; 81 in[Belong[v]]++; 82 } 83 } 84 85 long long ans=0; 86 87 for(int i=1;i<=scc;i++){ 88 if(in[i]==0||out[i]==0){ 89 ans=max(ans,(n*n-(n-NUM[i])*NUM[i]-n-m)); 90 } 91 } 92 93 //注意數(shù)據(jù)溢出的情況 94 95 printf("%lld\n",ans); 96 } 97 98 99 int main(){ 100 int T; 101 scanf("%d",&T); 102 for(int i=1;i<=T;i++){ 103 104 init(); 105 int n,m; 106 scanf("%d%d",&n,&m); 107 for(int j=0;j<m;j++){ 108 int u,v; 109 scanf("%d%d",&u,&v); 110 addEdge(u,v); 111 } 112 printf("Case %d: ",i); 113 solve(n,m); 114 115 } 116 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/IKnowYou0/p/6539134.html

總結(jié)

以上是生活随笔為你收集整理的HDU 4635 Strongly connected的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。