1. 求一个n点m边的图，选择k条边，满足没有环，最多获得价值。

$n, m \leq 100000$

【题解】类似于kruskal操作就可以了。

# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <iostream>

using namespace std;

int n, m, k, fa[300010], cnt=0;
long long ans = 0;
struct edge {
	int u, v, w;
}e[300010];

inline int getf(int x) {
	return x == fa[x] ? x : fa[x] = getf(fa[x]);
}

inline bool cmp(edge a, edge b) {
	return a.w>b.w;
}


int main() {
	freopen("carpet.in", "r", stdin);
	freopen("carpet.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &k);
	for (int i=1; i<=n; ++i) fa[i]=i;
	for (int i=1; i<=m; ++i) 
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	sort(e+1, e+m+1, cmp);
	for (int i=1; i<=m; ++i) {
		int fu = getf(e[i].u), fv = getf(e[i].v);
		if(fu != fv) {
			fa[fu] = fv;
			++cnt;
			ans = ans + e[i].w;
		}
		if(cnt == k) break;
	}
	
	cout << ans << endl;
	return 0;
}

2. $f(x, y) = f(x-1, y) \times f(x, y-1) (x, y \not= 0)$。

当$x=0$时，$f(0, y) = 1$。当$y=0$时，$f(x, 0)=x$

求$f(n, m)$的因数个数。

$n \leq 1000, m \leq 100$

【题解】可以发现，最后实质上对答案有影响的，都是类似于$f(x, 0)$的值。这样我们就可以用一种类似于杨辉三角的东西转移下来。然后分别统计即可。

# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>

using namespace std;

int n, k;
long long f[1010][110], ans;
const long long MOD=1e9+9;
long long cnt[66666];
inline void getys(int x, long long times) {
	for (int i=2; x>=i; ++i) {
		if(x%i == 0)
			while(x%i == 0) cnt[i] = cnt[i] + times, x=x/i;
	}
}

int main() {
	freopen("calc.in", "r", stdin);
	freopen("calc.out", "w", stdout);
	scanf("%d%d", &n, &k);
	f[n][k] = 1;
	for (int i=n; i>=1; --i)
		for (int j=k; j>=1; --j) {
			if(i == n && j == k) continue;
			f[i][j] = (f[i+1][j] + f[i][j+1]) % MOD;
		}

	ans = 1;
	for (int i=1; i<=n; ++i) 
		getys(i, f[i][1]);
	
	for (int i=2; i<=n; ++i)
		if(cnt[i] != 0) ++cnt[i], cnt[i] %= MOD;
	
	for (int i=2; i<=n; ++i) if(cnt[i] != 0) ans = ans * cnt[i] % MOD;
	
	cout << ans << endl;
	return 0;
}

3. 

【题解】

乱搞即可。预处理连边跑spfa。

# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <queue>
# include <iostream>

using namespace std;

int n, m, c, s, t;

int tot2=0, head2[1010], next2[60100], to2[60100], w2[60100], b2[60100];
int p[100], r[100][100];
long long q[100][100];
int tot=0, head[210], to[700010], next[700010], w[700010], vis[210];
long long d[210];
queue<int> Q;

inline int get(int C, int x) {
	int res = 0;
	for (int i=1; i<=p[C]; ++i) {
		if(x <= q[C][i]) {
			res = res + (x-q[C][i-1]) * r[C][i];
			break;
		} else res = res + (q[C][i]-q[C][i-1])*r[C][i];	
	}
	return res;
}

inline void add2(int x, int y, int z, int b) {
	++tot2; next2[tot2] = head2[x];
	head2[x] = tot2;
	to2[tot2] = y;
	w2[tot2] = z;
	b2[tot2] = b;
}


inline void add(int x, int y, int z) {
	++tot;
	next[tot]=head[x];
	head[x]=tot;
	to[tot]=y;
	w[tot]=z;
}

int start;

/*
inline void dfs(int x, int father, int belong, int cd) {
	for (int i=head2[x]; i; i=next2[i]) {
		if(to2[i] == father) continue;
		if(belong == -1) {
			add(start, to2[i], get(b2[i], w2[i]));
//			printf("ADD! start = %d, end = %d, length = %d\n", start, to2[i], get(b2[i], w2[i]));
			dfs(to2[i], x, b2[i], cd+w2[i]);
		} else {
			if(belong == b2[i]) {
				add(start, to2[i], get(belong, cd+w2[i]));
//				printf("ADD! start = %d, end = %d, length = %d\n", start, to2[i], get(belong, cd+w2[i]));
				dfs(to2[i], x, belong, cd+w2[i]);
			}
		}
	}
}
*/

inline void getmindis(int s, int belong) {
	while(!Q.empty()) Q.pop();
	Q.push(s);
	for(int i=1; i<=n; ++i) vis[i]=0, d[i]=10000000000000LL;
	d[s]=0, vis[s]=1;
	while(!Q.empty()) {
		int top=Q.front(); Q.pop(); vis[top]=0;
		for (int i=head2[top]; i; i=next2[i])
			if(b2[i] == belong && d[to2[i]] > d[top] + w2[i]) {
				d[to2[i]] = d[top] + w2[i];
				if(!vis[to2[i]]) {
					vis[to2[i]] = 1;
					Q.push(to2[i]);
				}
			}
	}
	for (int i=1; i<=n; ++i)
		if(i!=s && d[i] < 10000000000000LL) //{
			add(s, i, get(belong, d[i]));
//			printf("ADD! START=%d, END=%d, DIS=%d\n", s, i, get(belong, d[i]));
//		}
}


int main() {
	freopen("railway.in", "r", stdin);
	freopen("railway.out", "w", stdout);
	
	scanf("%d%d%d%d%d", &n, &m, &c, &s, &t);
	for (int i=1, x, y, z, b; i<=m; ++i)  {
		scanf("%d%d%d%d", &x, &y, &z, &b);
		add2(x, y, z, b);
		add2(y, x, z, b);
	}
	
	for (int i=1; i<=c; ++i) scanf("%d", &p[i]);
	for (int i=1; i<=c; ++i) {
		q[i][0]=0;
		for (int j=1; j<=p[i]-1; ++j) scanf("%d", &q[i][j]);
		q[i][p[i]] = 10000000000000LL;
		for (int j=1; j<=p[i]; ++j) scanf("%d", &r[i][j]);
	}
	
	for (int i=1; i<=n; ++i) {
		start = i;
		for (int j=1; j<=c; ++j)
			getmindis(i, j);
	}
	
	for(int i=1; i<=n; ++i) vis[i]=0, d[i]=10000000000000LL;
	while(!Q.empty()) Q.pop();
	Q.push(s);vis[s]=1;d[s]=0;
	while(!Q.empty()) {
		int top=Q.front(); Q.pop();
		vis[top]=0;
		for (int i=head[top]; i; i=next[i]) {
			if(d[top] + w[i] < d[to[i]]) {
				d[to[i]] = d[top] + w[i];
				if(!vis[to[i]]) {
					vis[to[i]] = 1;
					Q.push(to[i]);
				}
			}
		}
	}

	cout << (10000000000000LL == d[t] ? -1 : d[t]) << endl;
	return 0;
}