Post 15

Veröffentlicht am | Edited on

The easy is downhill.

盒子与小球之四

描述

给定N个各不相同的小球，和M个不同的BOX，有多少种不同的放球方法，使得每个BOX里的小球个数不小于Ｋ。N,M,K均小于15

输入

每行给出Ｎ,M,K

以0 0 0结束

输出

如题

样例输入

1
2
3
4
3 3 1
2 4 1
3 2 0
0 0 0

样例输出

1
2
3
6
0
8

题解

这题一开始想组合数学做法，结果发现怎么都会重。。。

既然这样那不如就写个组合dp好了。

设$f(i,j)$表示前$i$个小球放入$j$个盒子中的方案数。

显然我们只需要枚举当前盒子放了几个球。

n-i+p是因为我们要在剩下的球(前面状态带编号选了i-p个球)中选择p个球。

一开始组合数还写错了。。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 20
#define ll long long
ll f[maxn][maxn] , c[maxn][maxn];
int n , m , k;
inline void pre()
{
	for(int i = 0 ; i <= 15 ; ++i)
		c[i][0] = c[i][i] = 1;
	for(int i = 2 ; i <= 15 ; ++i)
		for(int j = 1 ; j <= 15 ; ++j)
			c[i][j] = c[i-1][j-1] + c[i-1][j];
}
int main()
{
	pre();
	while(scanf("%d%d%d",&n,&m,&k) != EOF)
	{
		if(n == 0 && m == 0 && k == 0)	break;
		if(n < m * k) {
			puts("0");
			continue;
		}
		std::memset(f,0,sizeof(f));
		for(int i = k; i <= n ; ++i)
			f[i][1] = c[n][i];
		for(int i = k ; i <= n ; ++i)
			for(int j = 2 ; j <= m ; ++j)
				for(int t = k ; t <= i ; ++t)
					f[i][j] += f[i-t][j-1] * c[n-i+t][t];
		printf("%lld\n",f[n][m]);
	}
}

UVA11324 The Largest Clique

题目描述

给你一张有向图 G，求一个结点数最大的结点集，使得该结点集中的任意两个结点 u 和 v 满足：要么 u 可以达 v，要么 v 可以达 u（u,v相互可达也行）。

输入数据

第一行：测试数据组数T，每组数据的格式如下：
第一行为结点数 n 和边数 m ，结点编号 1~n。
以下m行每行两个整数 u 和 v ，表示一条有向边 u->v。

输出数据

每组数据输出最大结点集的结点数

题解

是一道很水的题目(⊙o⊙)…

显然只需要根据一个非常容易得知的性质：有向图上一个点u能到另一点v，那所有到达点u的点都能到v。

这启发我们要用拓扑排序。

又考虑到图中有强联通分量ECC。

ECC内任意两点均可互相到达，满足题意，可以视为一个“大点”

因此先Tarjan缩点在写一个简单的dp就可以AC了

u是能够到达点v的点。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <cstring>
#include <queue>
#include <iostream>
#define maxn 1005
int head[maxn] , ct , n , m, t , ecc[maxn] , ans , sz[maxn] , f[maxn] , tot , d[maxn];
bool ins[maxn];
struct edge{
	int next , to;
}e[maxn<<9];
struct tmp{
	int fr , to;
}er[maxn<<9];
inline void add(int x , int y)
{
	e[++ct].next = head[x];
	e[ct].to = y;
	head[x] = ct;
	++d[y];
}
namespace FNT
{
	int dfn[maxn] , low[maxn] , idx;
	std::stack<int> st;
	void Tarjan(int x)
	{
		dfn[x] = low[x] = ++idx;
		st.push(x);
		ins[x] = true;
		for(int i = head[x] ; i ; i = e[i].next)
		{
			int v = e[i].to;
			if(!dfn[v]) Tarjan(v) , low[x] = std::min(low[x] , low[v]);
			else if(ins[v]) low[x] = std::min(low[x] , dfn[v]);
		}
		if(dfn[x] == low[x])
		{
			++tot;
			while(st.top() != x)
			{
				ecc[st.top()] = tot;
				sz[tot] ++;
				ins[st.top()] = false;
				st.pop();
			}
			ecc[st.top()] = tot;
			ins[st.top()] = false;
			sz[tot] ++;
			st.pop();
		}
	}
}
inline void dp()
{
	std::queue<int> q;
	for(int i = 1 ; i <= tot ; ++i)
		f[i] = sz[i];
	for(int i = 1 ; i <= tot ; ++i)
		if(!d[i]) q.push(i);
	while(!q.empty())
	{
		int k = q.front();
		q.pop();
		for(int i = head[k] ; i ; i = e[i].next)
		{
			int v = e[i].to;
			f[v] = std::max(f[v] , f[k] + sz[v]);
			if(!(--d[v])) q.push(v);
		}
	}
}
inline void init()
{
	std::memset(head,0,sizeof(head));
	std::memset(ecc,0,sizeof(ecc));
	std::memset(FNT::dfn,0,sizeof(FNT::dfn));
	std::memset(FNT::low , 0, sizeof(FNT::low));
	std::memset(sz,0,sizeof(sz));
	std::memset(f,0,sizeof(f));
	std::memset(d,0,sizeof(d));
	std::memset(ins,false,sizeof(ins));
	FNT::idx = 0 ,ct = 0 , tot = 0 , ans = 0;
}
int main()
{
	scanf("%d",&t);
	while(~(--t))
	{
		scanf("%d%d",&n,&m);
		init();
		for(int i = 1 ; i <= m ; ++i)
		{
			int x , y;
			scanf("%d%d",&x,&y);
			add(x,y) , er[i].fr = x , er[i].to = y;
		}
		for(int i = 1 ; i <= n ; ++i)
			if(!FNT::dfn[i]) FNT::Tarjan(i);
		std::memset(d,0,sizeof(d));
		std::memset(head,0,sizeof(head));
		ct = 0;
		for(int i = 1 ; i <= m ; ++i)
		{
			int u = er[i].fr  , v = er[i].to;
			if(ecc[v] != ecc[u]) add(ecc[u] , ecc[v]);
		}
		dp();
		for(int i = 1 ; i <= tot ; ++i)
			ans = std::max(ans , f[i]);
		printf("%d\n",ans);
	}
}

[ZJOI2007]最大半连通子图

题目描述

一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：?u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G’=(V’,E’)满足V’?V，E’是E中所有跟V’有关的边，则称G’是G的一个导出子图。若G’是G的导出子图，且G’半连通，则称G’为G的半连通子图。若G’是G所有半连通子图中包含节点数最多的，则称G’是G的最大半连通子图。给定一个有向图G，请求出G的最大半连通子图拥有的节点数K，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。

输入输出格式

输入格式：

第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。

输出格式：

应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

输出样例#1：

1
2
3
3

说明

对于100%的数据，

题解

比起上面那道题多了个方案数。

有没有想到最短路计数？显然严格大于就改成当前更新点的方案数，恰好等于就加上方案数。

所以要考虑重边！用map去重居然没有TLE，假如TLE也不是没办法，换成vector排序即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <cstring>
#include <map>
#define maxn 100005
#define ll long long
int head[maxn] , tot , ct , n , m , d[maxn] , mod , f[maxn] , sz[maxn] , ecc[maxn];
ll g[maxn] ;
std::map<int,int> vis[maxn];
bool ins[maxn];
struct edge{
	int next , to;
}e[maxn<<4];
struct Emmm{
	int fr , to;
}er[maxn<<4];
inline void add(int x , int y)
{
	e[++ct].next = head[x];
	e[ct].to = y;
	head[x] = ct;
	++d[y];
}
namespace FNT
{
	int dfn[maxn] , low[maxn] , idx;
	std::stack<int> st;
	void Tarjan(int x)
	{
		dfn[x] = low[x] = ++idx;
		st.push(x);
		ins[x] = true;
		for(int i = head[x] ; i ; i = e[i].next)
		{
			int v = e[i].to;
			if(!dfn[v]) Tarjan(v) , low[x] = std::min(low[x] , low[v]);
			else if(ins[v]) low[x] = std::min(low[x] , dfn[v]);
		}
		if(dfn[x] == low[x])
		{
			++tot;
			while(st.top() != x)
			{
				ecc[st.top()] = tot;
				sz[tot] ++;
				ins[st.top()] = false;
				st.pop();
			}
			ecc[st.top()] = tot;
			ins[st.top()] = false;
			sz[tot] ++;
			st.pop();
		}
	}
}
inline void dp()
{
	std::queue<int> q;
	for(int i = 1 ; i <= tot ; ++i)
		f[i] = sz[i] , g[i] = 1;
	for(int i = 1 ; i <= tot ; ++i)
		if(!d[i]) q.push(i);
	while(!q.empty())
	{
		int k = q.front();
		q.pop();
		for(int i = head[k] ; i ; i = e[i].next)
		{
			int v = e[i].to;
			if(f[k] + sz[v] > f[v])
			{
				g[v] = g[k];
				f[v] = f[k] + sz[v];
			}
			else if(f[k] + sz[v] == f[v])	(g[v] += g[k]) %= mod;
			if(!(--d[v])) q.push(v);
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&mod);
	for(int i = 1 ; i <= m ; ++i)
	{
		int x , y;
		scanf("%d%d",&x,&y);
		add(x,y) , er[i].fr = x , er[i].to = y;
	}
	for(int i = 1 ; i <= n ; ++i)
		if(!FNT::dfn[i]) FNT::Tarjan(i);
	std::memset(head,0,sizeof(head));
	std::memset(d,0,sizeof(d));
	ct = 0;
	for(int i = 1 ; i <= m ; ++i)
	{
		int u = er[i].fr , v = er[i].to;
		if(ecc[u] != ecc[v] && !vis[ecc[u]][ecc[v]]) add(ecc[u] , ecc[v]) , vis[ecc[u]][ecc[v]] = 1;
	}
	dp();
	int ans1 = 0 ;
    ll	ans2 = 0;
	for(int i = 1 ; i <= tot ; ++i)
	{
		if(ans1 < f[i]) ans1 = f[i] , ans2 = g[i] % mod;
		else if(ans1 == f[i]) (ans2 += g[i]) %= mod;
	}
	printf("%d\n%lld",ans1,ans2);
}

今天就此结束，明天也要认真学习哦！