POJ1737 Connected Graph

###Description

An undirected graph is a set V of vertices and a set of E∈{V*V} edges.An undirected graph is connected if and only if for every pair (u,v) of vertices,u is reachable from v. 
You are to write a program that tries to calculate the number of different connected undirected graph with n vertices. 
For example,there are 4 different connected undirected graphs with 3 vertices.

###Input

The input contains several test cases. Each test case contains an integer n, denoting the number of vertices. You may assume that 1<=n<=50. The last test case is followed by one zero.
###Output

For each test case output the answer on a single line.
###Sample Input

1
2
3
4
0
###Sample Output

1
1
4
38

题意：统计n个点的带标号无向连通图个数。
从正面不好考虑我们可以从反面考虑。因为n个点的无向图有多少种是很好求的，我们可不可以用总的减去不连通的呢？
考虑计算不连通的图的种类。为了不算重，我们假设先固定一个点，那么这个点一定在这个图的一个无向连通子图(连通块)内。那我们就可以枚举这个点所在的连通子图的大小了。便有了状态转移方程：
$$dp[i] = 2^{\binom i 2} - \sum^{i - 1}_{j = 1}dp[j]*{\binom {i-1} {j-1}}*2^{\binom {i-j} 2}$$

简述其含义即用总的无向图种数减去不连通图个数。不连通图个数可以固定一个点枚举其所在连通块大小，这其中我们可以从剩下$i-1$个点种选出$j-1$个放入这个连通块。再考虑剩下的$i-j$个点，因为只要选出来成为当前枚举的连通块内的点不一样了，那么这两张带标号图一定不同。并且$i-j$个点组成的图和当前连通块一定没有连边。那么分开考虑，剩下的$i-j$个点组成任何种类的图都是合法的。

不知道为什么本机通过上交就re了，打表大法好。

AC代码：
```
#include<cstdio>
using namespace std;
char ans[][2005] = {
"1",
"1",
"4",
"38",
"728",
"26704",
"1866256",
"251548592",
"66296291072",
"34496488594816",
"35641657548953344",
"73354596206766622208",
"301272202649664088951808",
"2471648811030443735290891264",
"40527680937730480234609755344896",
"1328578958335783201008338986845427712",
"87089689052447182841791388989051400978432",
"11416413520434522308788674285713247919244640256",
"2992938411601818037370034280152893935458466172698624",
"1569215570739406346256547210377768575765884983264804405248",
"1645471602537064877722485517800176164374001516327306287561310208",
"3450836972295011606260171491426093685143754611532806996347023345844224",
"14473931784581530777452916362195345689326195578125463551466449404195748970496",
"121416458387840348322477378286414146687038407628418077332783529218671227143860518912",
"2037032940914341967692256158580080063148397956869956844427355893688994716051486372603625472",
"68351532186533737864736355381396298734910952426503780423683990730318777915378756861378792989392896",
"4586995386487343986845036190980325929492297212632066142611360844233962960637520118252235915249481987129344",
"615656218382741242234508631976838051282411931197630362747033724174222395343543109861028695816566950855890811486208",
"165263974343528091996230919398813154847833461047104477666952257939564080953537482898938408257044203946031706125367800496128",
"88725425253946309579607515290733826999038832348034303708272765654674479763074364231597119435621862686597717341418971119460584259584",
"95268202520385449790227094691687836722278710954949736428196756305746453532341035148366531266372862653739009088659598082113309304400438624256",
"204586909944926298207861553173799965921067126517774603507480126827588404754232387878919170016875623577048105576068684204467114231315623298308706926592",
"878694093745349914731889727208157807680003171098920968952145189548012830636076748530741378813207711246134152874638123892704663922045456803250047261786444398592",
"7547924819767483287594694542205326068855891655862820018679189530528628155893698967796630219069788201405972928386025644172169109953194652176102437455457970998547197198336",
"129672361263353660216004848405397154497075914498088480263529787446798464815868889966259599220355751574955667311875199310825316757090836792227021420332597263591744872066219249762304",
"4455508410978470003213152055317479855991723332650114280703483486331017198541367912550307040027205813596014620050254013798901452927850711294962075802234712748298505435020109941966616435621888",
"306180206751230090930313674296749763317292930219833760674864513181351793147422958983304199997791891477494238067606067864147691875149221011750587805454462256284237767964756224079011437145490032917741568",
"42081087200752140195116730773102052524009718837902621183664949269856744858385083976643391056195246283737633254986683196506525739229100562028667655727478159896469450443625002559600024194689577683162985133342982144",
"11567161173227696466220457283329529101751379197153495724502457893891478829937149071434453800538222228465001645119757350054456753856800058471020811256328606811309950183460999195585736337722940242137574318489684508433109221376",
"6359114105601017351375465630036218352726964545083913061809864302427743340641476112983635151514041188995967358659226381513838435962182371853731281705837980150384424607870600516842502175922529566100381861494213531965265765000213275082752",
"6991919901710702396948942815573257427744311018004588489866790612959056357721564695830748688904669995738081555372234543689358610668809196548322563461899302515136978058611651369187392760821440875968116963440793130046454847480988052748303630065467392",
"15375394465098365435098131065240195173750887603455691084898736566282027607324662718653380384318359771738669872579070523864682029424324656980343742654131923883848453279046887366030428581980234722002609397042921130626427482776226373410811403774539364168814821376",
"67621699984704009571087635348261788647460730411971168452281282746962798999895717916292043207408657855232972628889146834646084600650980317820241001687549180689983916950502853108787655643356237905731863505593837387547463783553663104052737827256888296815897621036524900450304",
"594806763388137870319868932592503661181879874998563369872608575294390559331829154567126246824792929668641338543467328561106071308881273503814138669414317911219402066314092130747535752627679688399993515689603622744525243838714230998285264232171322066511990049433899384262102238508351488",
"10463951242026625501784363274596214619943325701401522513836100192928357652762255136769619473700702276949844553770347735730521468871772581157963359677917896206658361141741863952608795675733168160935829452838892433190712974942475048711118429563334205007874224852816312589287727030417085994911901155328",
"368167554019320956145827247050509963076959450983143444578072117098399777382502455552633802915095691807005512740224345254318634273382517137823997743877511866703540358482988273801636313118482363728678083259725882776454656507629131210255280738244476783496709369751571318821222548711309212127848471930415455355797504",
"25907488423318455274080473672019976083009208996271003791416218114322853582878049179546761491016196610119349803222490393175612695149120594742502991139032865749979736985340247224801444473477196529096332604358326020598992443433363048888842556850935198901353471923472154386768107635993449205071378228596636214817388982756553261056",
"3646154850293767810262810894999553363628589110640769385457986485984919161321600546344826908488589572223649058216506920510786720770519258252897810249930214560211056122090333850686659187132094273815095247787669459869137017783625755540375408272361426098383313551230976557640520636974573279383371834513917048967432546435999569365350430111956992",
"1026301351570055077911628972867042177680735585635225345203536190737910863123857244548313982876228994987864700400759811456244128889754306386459557887432298148719591734971030611474690885904247396313959818854940592795291449937598794070517570167551607950979266237997797283563645242105244737520881371410960067902176629829514256225641238164014573644333472284672",
"577756298062641319815321284633539861082132919998722885657507672188606317696301924134068233518707877841769252356274834883678320922291785288952259324960085933885572481476441044041666245632947630667669900623389069655523344952222114179660086674251300523449279256078271770682664276058349275922600493471476178420154378012048571333436567365397136152469165480980158369042006016"};
int main() {
	int n;
	while(1) {
		scanf("%d", &n);
		if(n == 0) break;
		else printf("%s\n", ans[n - 1]);
	}
}

```

计算代码：
```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define LL long long
using namespace std;
const int maxn = 50 + 5;
int N = 50;

namespace BIGINT {
	const int POW = 100000000, ML = 130, st = 8;
	char s[ML]; int len, tmp, tmp2;
	const int TP[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
	#define For(i, a, b) for(register int i = a; i <= b; ++i)
	#define Down(i, a, b) for(register int i = a; i >= b; --i)
	struct INT1024 {
		int a[ML], l;
		INT1024() {}
		void clear() {memset(a, 0, sizeof(int) * (l + 1)), l = 0;}
		INT1024(int x) {
			clear();
			while(x) a[l++] = x % POW, x /= POW;
		}
		void init(int x) {
			clear();
			while(x) a[l++] = x % POW, x /= POW;
		}
		void put() {
			printf("%d", a[l - 1]);
			Down(i, l - 2, 0) printf("%04d", a[i]);
		}
		void read() {
			scanf("%s", s), len = strlen(s);
			l = tmp2 = tmp = 0;
			Down(i, len - 1, 0) {
				tmp = tmp + (s[i] - '0') * TP[tmp2++];
				if(tmp2 == st) a[l++] = tmp, tmp2 = tmp = 0;
			}
			if(tmp) a[l++] = tmp;
		}
	} ;
	long long mid[ML << 1];
	INT1024 operator + (INT1024 a, const INT1024 &b) {
		a.l = max(a.l, b.l);
		For(i, 0, a.l - 1) a.a[i] += b.a[i];
		For(i, 0, a.l - 1) {
			a.a[i + 1] += a.a[i] / POW;
			a.a[i] %= POW;
		}
		while(a.a[a.l]) 
			a.a[a.l + 1] += a.a[a.l] / POW, a.a[(a.l++)] %= POW;
		return a;
	}
	INT1024 operator + (INT1024 a, const int &b) {
		a.a[0] += b;
		For(i, 0, a.l - 1) {
			a.a[i + 1] += a.a[i] / POW;
			a.a[i] %= POW;
		}
		while(a.a[a.l]) 
			a.a[a.l + 1] += a.a[a.l] / POW, a.a[(a.l++)] %= POW;
		return a;
	}
	void operator += (INT1024 & a, const int &b) {
		a.a[0] += b;
		For(i, 0, a.l - 1) {
			if(a.a[i] < POW) return ;
			a.a[i + 1] += a.a[i] / POW;
			a.a[i] %= POW;
		}
		while(a.a[a.l]) 
			a.a[a.l + 1] += a.a[a.l] / POW, a.a[(a.l++)] %= POW;
	}
	INT1024 operator - (INT1024 a, const INT1024 &b) {
		a.l = max(a.l, b.l);
		For(i, 0, a.l - 1) a.a[i] -= b.a[i];
		For(i, 0, a.l - 2) {
			if(a.a[i] < 0) a.a[i + 1] -= 1, a.a[i] += POW;
		}
		while(!a.a[a.l - 1]) --a.l;
		return a;
	}
	INT1024 operator - (INT1024 a, const int &b) {
		a.a[0] -= b;
		For(i, 0, a.l - 2) {
			if(a.a[i] < 0) a.a[i + 1] -= 1, a.a[i] += POW;
			else return a;
		}
		while(!a.a[a.l - 1]) --a.l;
		return a;
	}
	void operator -= (INT1024 & a, const int &b) {
		a.a[0] -= b;
		For(i, 0, a.l - 2) {
			if(a.a[i] < 0) a.a[i + 1] -= 1, a.a[i] += POW;
			else return ;
		}
		while(!a.a[a.l - 1]) --a.l;
	}
	long long tml;
	INT1024 operator / (INT1024 a, const int &b) {
		tml = 0;
		Down(i, a.l - 1, 0) {
			tml = tml * POW + a.a[i];
			a.a[i] = tml / b, tml %= b;
		}
		while(!a.a[a.l - 1]) --a.l;
		return a;
	}
	void operator /= (INT1024 & a, const int &b) {
		tml = 0;
		Down(i, a.l - 1, 0) {
			tml = tml * POW + a.a[i];
			a.a[i] = tml / b, tml %= b;
		}
		while(!a.a[a.l - 1]) --a.l;
	}
	INT1024 operator * (INT1024 a, const INT1024 &b) {
		int len = a.l + b.l;
		memset(mid, 0, sizeof(long long) * (len + 1));
		For(i, 0, a.l - 1) For(j, 0, b.l - 1)
			mid[i + j] += 1ll * a.a[i] * b.a[j];
		For(i, 0, len - 1) mid[i + 1] += mid[i] / POW, mid[i] %= POW;
		while(!mid[len - 1]) --len;
		a.l = len;
		For(i, 0, len - 1) a.a[i] = mid[i];
		return a;
	}
}

using namespace BIGINT;
INT1024 t, dp[maxn], two(2);
INT1024 C(int a, const int & b) {
	t.init(1);
	For(i, 1, b) {
		t = t * INT1024(a);
		a -= 1; 
	}
	For(i, 2, b) 
		t /= i;
	return t;
}

INT1024 pow2(int x) {
	t.init(1);
	while(x--) t = t * two;
	return t;
}

int n = 50, mx;
int main() {
	dp[1].init(1), mx = n * (n - 1) / 2;
	For(i, 1, n) dp[i] = pow2((i - 1) * i / 2); 
	For(i, 2, n) {
		For(j, 1, i - 1)
			dp[i] = dp[i] - pow2((i - j) * (i - j - 1) / 2) * dp[j] * C(i - 1, j - 1);
	}
	while(1) {
		scanf("%d", &n);
		if(!n) break;
		dp[n].put(), putchar('\n');
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链