http://acm.hdu.edu.cn/showproblem.php?pid=4635
我們把縮點(diǎn)后的新圖(實(shí)際編碼中可以不建新圖 只是為了概念上好理解)中的每一個(gè)點(diǎn)都賦一個(gè)值
表示是由多少個(gè)點(diǎn)縮成的 我們需要找所有端點(diǎn) 也可能出發(fā)點(diǎn)(只有出度) 也可能是結(jié)束點(diǎn) (只有入度)
這個(gè)端點(diǎn)和外界(其它所有點(diǎn))的聯(lián)通性是單向的(只入或只出) 也可能沒有聯(lián)通
在保持這個(gè)端點(diǎn)與外界的單向聯(lián)通性的情況下 任意加邊
所以?當(dāng)端點(diǎn)的值越小(包含點(diǎn)越少) 結(jié)果越優(yōu)
代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef pair<int,int> pp;
typedef long long ll;
const int N=100005;
const int M=100005;
int head[N],I;
struct node
{
int j,next;
}edge[M];
int low[N],dfn[N],f[N],deep;
bool in[N],visited[N];
stack<int>st;
pp p[M];
void add(int i,int j)
{
edge[I].j=j;
edge[I].next=head[i];
head[i]=I++;
}
bool ok(vector<int>& vt)
{
for(unsigned int i=0;i<vt.size();++i)
{
int x=vt[i];
for(int t=head[x];t!=-1;t=edge[t].next)
{
int y=edge[t].j;
if(f[x]!=f[y])
return false;
}
}
return true;
}
void tarjan(int x,int &M)
{
visited[x]=true;
in[x]=true;
st.push(x);
low[x]=dfn[x]=deep++;
for(int t=head[x];t!=-1;t=edge[t].next)
{
int j=edge[t].j;
if(visited[j]==false)
{
tarjan(j,M);
low[x]=min(low[x],low[j]);
}else if(in[j]==true)
{
low[x]=min(low[x],dfn[j]);
}
}
if(low[x]==dfn[x])
{
vector<int>vt;
int tmp=1;
while(st.top()!=x)
{
int k=st.top(); st.pop();
vt.push_back(k);
in[k]=false;
f[k]=x;
++tmp;
}
int k=st.top(); st.pop();
vt.push_back(k);
in[k]=false;
f[k]=x;
if(ok(vt))
{
M=min(M,tmp);
}
}
}
void init(int n,int m)
{
memset(head,-1,sizeof(head));
I=0;
for(int i=0;i<m;++i)
add(p[i].first,p[i].second);
}
int solve(int n,int m)
{
init(n,m);
while(!st.empty()) st.pop();
for(int i=1;i<=n;++i)
{f[i]=i;}
memset(in,false,sizeof(in));
memset(visited,false,sizeof(visited));
deep=0;
int k=n+1;
for(int i=1;i<=n;++i)
if(!visited[i])
tarjan(i,k);
return k;
}
int main()
{
//freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
for(int ca=1;ca<=T;++ca)
{
printf("Case %d: ",ca);
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<m;++i)
scanf("%d %d",&p[i].first,&p[i].second);
int k=solve(n,m);
for(int i=0;i<m;++i)
swap(p[i].first,p[i].second);
k=min(solve(n,m),k);
if(k==n)
{cout<<"-1"<<endl;continue;}
ll ans=0;
ans=(ll)(n)*(ll)(n-1);
ans-=m;
ans-=(ll)(k)*(ll)(n-k);
cout<<ans<<endl;
}
return 0;
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
