CRITICAL - Thành phố trọng yếu

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#define MAX   20020
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
typedef long long ll;
vector<int> g[MAX];
int low[MAX];
int num[MAX];
int ncp[MAX];
int nc[MAX];
int sz[MAX];
int n,m,cnt;
ll sp;
void minimize(int &x,const int &y) {
	if (x>y) x=y;
}
void loadgraph(void) {
	scanf("%d",&n);
	scanf("%d",&m);
	REP(i,m) {
		int u,v;
		scanf("%d",&u);
		scanf("%d",&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}	
}
ll sumproduct(const vector<int> &v) {
	int sumall=0;
	ll sumsqr=0LL;
	FORE(it,v) {
		sumall+=*it;
		sumsqr+=1LL*(*it)*(*it);
	}
	return (1LL*sumall*sumall-sumsqr)/2;
}
int BFS(int s,int id) {
	queue<int> q;
	while (!q.empty()) q.pop();
	ncp[s]=id;
	q.push(s);
	int ret=1;
	while (!q.empty()) {
		int u=q.front();q.pop();
		FORE(it,g[u]) if (ncp[*it]==0) {
			ncp[*it]=id;
			q.push(*it);
			ret++;
		}
	}
	return (ret);
}
void visit(int u) {
	vector<int> nchild=vector<int>();
	int nrest=0;
	cnt++;	
	low[u]=n+7;
	num[u]=cnt;
	FORE(it,g[u]) {
		int v=*it;
		if (num[v]==0) {
			visit(v);
			nc[u]+=nc[v];
			if (low[v]>=num[u]) nchild.push_back(nc[v]);
			else nrest+=nc[v];
			minimize(low[u],low[v]);
		}
		else minimize(low[u],num[v]);
	}
	nc[u]++;
	nrest+=sz[ncp[u]]-nc[u];
	nchild.push_back(nrest);
	sp+=sumproduct(nchild);
}
void process(void) {
	int tmp=0;
	FOR(i,1,n) if (ncp[i]==0) {
		tmp++;
		sz[tmp]=BFS(i,tmp);
	}
	FOR(i,1,n) if (num[i]==0) visit(i);
	printf("%.2lf",1.0*sp/n);
}
int main(void) {
	loadgraph();
	process();
	return 0;
}

Download