2272.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2272 on 2006-08-10 at 16:57:30 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
typedef long long int64;
const int CN = 128;
 
class Graph {
private:
	bool road[CN][CN];
	int n, d, sc[CN], id[CN];
	int low[CN], dfn[CN], stack[CN], top, cnt, scnt;
	void scR(int);
public:
	bool make();
	int64 place();
};
bool Graph::make() {
	int m, i;
	if(scanf("%d %d %d", &n, &m, &d) != 3) return false;
	memset(road, false, sizeof(road));
	for(i = 0; i < m; i++) {
		int a, b; scanf("%d %d", &a, &b);
		road[a-1][b-1] = true;
	}
	top = cnt = scnt = 0; memset(dfn, -1, sizeof(dfn));
	return true;
}
void Graph::scR(int u) {
	stack[top++] = u;
	int i, h = dfn[u] = low[u] = cnt++;
	for(i = 0; i < n; i++) {
		if(!road[u][i]) continue;
		if(dfn[i] == -1) scR(i);
		h = min(h, low[i]);
	}
	if(h != low[u]) { low[u] = h; return; }
	sc[scnt] = 0;
	while(true) {
		int p = stack[--top];
		sc[scnt]++; id[p] = scnt; low[p] = CN;
		if(p == u) break;
	}
	scnt++;
}
int64 Graph::place() {
	if(d > n) return 0;
	else if(d == n) return 1;
	int i, j, k;
	for(i = 0; i < n; i++)
		if(dfn[i] == -1) scR(i);
	int ind[CN] = { 0 }, oud[CN] = { 0 }, u[CN] = { 0 };
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			if(id[i] != id[j] && road[i][j]) { ind[id[j]]++; oud[id[i]]++; }
	for(i = 0; i < scnt; i++)
		if(!ind[i] || !oud[i]) u[i] = 1;
	int64 pst[CN][CN] = { 1 };
	for(i = 0; i < n && !u[i]; i++) pst[i+1][0] = 1;
	for(i = 1; i <= d; i++) {
		for(j = 1; j <= scnt; j++) {
			int64 ck = u[j-1]?sc[j-1]:1; int lmt = min(sc[j-1], i);
			for(k = u[j-1]; k <= lmt; k++) {
				pst[j][i] += pst[j-1][i-k]*ck;
				ck = ck*(sc[j-1]-k)/(k+1);
			}
		}
	}
	return pst[scnt][d];
}
 
int main()
{
	Graph g;
	
	while(g.make()) printf("%lld\n", g.place());
	
	return 0;
}