太原网站排名公司,郑州网站建设企业推荐,app源码论坛,做电影网站配什么公众号题目:给出一个有向图,要求添加最多的边数,使得图仍然不强连通. 思路:首先这个图在添加边之后肯定变成了两个强连通分量,现在就看怎么分.然后我们可以注意到,原图进行强连通分量分解之后必然存在一些分量的出度或入度为0,最小的分量肯定在这些分量之中.那么找出这个分量就可以得…题目:给出一个有向图,要求添加最多的边数,使得图仍然不强连通. 思路:首先这个图在添加边之后肯定变成了两个强连通分量,现在就看怎么分.然后我们可以注意到,原图进行强连通分量分解之后必然存在一些分量的出度或入度为0,最小的分量肯定在这些分量之中.那么找出这个分量就可以得出的结果了. /*
* author: Cwind
*/
//#pragma comment(linker, /STACK:102400000,102400000)
#include iostream
#include map
#include algorithm
#include cstdio
#include cstring
#include cstdlib
#include vector
#include queue
#include stack
#include functional
#include set
#include cmath
using namespace std;
#define IOS std::ios::sync_with_stdio (false);std::cin.tie(0)
#define pb push_back
#define PB pop_back
#define bk back()
#define fs first
#define se second
#define sq(x) (x)*(x)
#define eps (1e-7)
#define IINF (129)
#define LINF (1ll59)
#define INF 1000000000
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
typedef pairll,ll P;
inline void debug_case(){static int cas1;printf(---------------Case #:%d------------------\n,cas);cas;
}
const int maxn1e5300;
int T;
int n,m;
vectorint G[maxn];
int dfn[maxn];
int clo;
int inscc[maxn],stk[maxn],low[maxn],top,sccid,cnt[maxn];
bool instk[maxn];
void tarjan(int v,int f){low[v]dfn[v]clo;stk[top]v;instk[v]1;for(int i0;iG[v].size();i){int uG[v][i];if(!dfn[u]){tarjan(u,v);low[v]min(low[v],low[u]);}else if(instk[u]){low[v]min(low[v],dfn[u]);}}if(low[v]dfn[v]){sccid;do{inscc[stk[--top]]sccid;cnt[sccid];instk[stk[top]]0;}while(stk[top]!v);}
}
int d1[maxn],d2[maxn];
void init(){for(int i0;in;i){G[i].clear();d2[i]d1[i]cnt[i]dfn[i]0;}sccidtopclo0;
}
int cas0;
int main(){freopen(/home/files/CppFiles/in,r,stdin);//freopen(defense.in,r,stdin);//freopen(defense.out,w,stdout);cinT;while(T--){// debug_case();scanf(%d%d,n,m);init();for(int i0;im;i){int a,b;scanf(%d%d,a,b);G[a].pb(b);}for(int i1;in;i){if(!dfn[i]) tarjan(i,-1);}for(int i1;in;i){for(int j0;jG[i].size();j){int uG[i][j];if(inscc[u]!inscc[i]){d1[inscc[u]];d2[inscc[i]];}}}int minn1e9;for(int i1;isccid;i){if(d1[i]0) minnmin(minn,cnt[i]);if(d2[i]0) minnmin(minn,cnt[i]);}ll an-minn,bminn;ll ans(ll)n*(n-1)-(ll)a*b-(ll)m;if(sccid1) ans-1;printf(Case %d: %lld\n,cas,ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/Cw-trip/p/4828674.html
