A - 迷宫

给出一个带权有向图，翻转一条边的代价是其权重，求出翻转边后图中无环的最小代价

二分 拓扑判环
一开始只能想到要让图中没有环，但是想不清楚怎么操作，于是等到题解emmmm
考虑对于要改变的边，相当于删去之后反向加回来，那么代价就是边里面权值最大的
二分权值，权值越大的可以改变的边越多，二分最少的代价使得不存在环即可

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
int n,m;
int u,v;
ll w;
int top[maxn],in[maxn];

vector<Edge> G1;
vector<int> edges[maxn];

bool check(ll now){
	int cnt = 0;
	for(int i = 1;i <= n;i++) edges[i].clear();
	mst(in,0);
	mst(top,0);
	for(int i = 0;i < m;i++){
		if(G1[i].dist > now){
			edges[G1[i].from].push_back(G1[i].to);
			in[G1[i].to] ++;
		}
	}
	queue<int> q;
	for(int i = 1;i <= n;i++) if(in[i] == 0) q.push(i),top[i] = ++cnt;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		int len = edges[u].size();
		for(int i = 0;i < len;i++){
			int v = edges[u][i];
			in[v] --;
			if(!in[v]) q.push(v),top[v] = ++cnt;
		}
	}
	for(int i = 1;i <= n;i++) if(in[i] != 0) return false;
	return true;
}

int main(){
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		cin>>u>>v>>w;
		G1.push_back(Edge(u,v,w));
	}
	ll l = 0,r = 2e9,mid,ans;
	while(l <= r){
		mid = (l + r) >> 1;
		if(check(mid)){
			r = mid - 1;
			ans = mid;
		}
		else l = mid + 1;
	}
	cout<<ans<<endl;
	return 0;
}
B - oydy的征途I

给定一个带权无向图，求出最小生成树但是其中某一条边可以0权值，已经可能的最小权值和的总数

最小生成树
先求出最小生成树，把最大权的边删去之后，求剩下的边的连通性
时间复杂度$ O(mlogm) $

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
int n,m;
int u,v,cnt,maxx = 0,ans = 0;
ll sum = 0,w;
int fa[maxn];
vector<Edge> G;

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

int main(){
	cin>>n>>m;
	for(int i = 1;i <= n;i++) fa[i] = i;
	cnt = n;
	for(int i = 1;i <= m;i++){
		cin>>u>>v>>w;
		G.push_back(Edge(u,v,w));
	}
	sort(G.begin(),G.end());
	for(int i = 0;i < m;i++){
		u = G[i].from,v = G[i].to;
		u = tfind(u),v = tfind(v);
		if(u != v){
			fa[v] = u;
			cnt --;
			sum += G[i].dist;
			if(cnt == 1) {
				sum -= G[i].dist;
			    maxx = G[i].dist;
			    break;
		    }
		}
		else continue;
	}
	for(int i = 1;i <= n;i++) fa[i] = i;
	for(int i = 0;i < m;i++){
		if(G[i].dist >= maxx) break;
		u = G[i].from,v = G[i].to;
		u = tfind(u),v = tfind(v);
		if(u != v){
			fa[v] = u;
		}
	}
	for(int i = 0;i < m;i++){
		if(G[i].dist < maxx) continue;
		u = G[i].from,v = G[i].to;
		u = tfind(u),v = tfind(v);
		if(u != v) ans ++;
	}
	cout<<sum<<" "<<ans<<endl;
	return 0;
}
C - oydy的征途II

给定一个有向图，如果存在欧拉路径的话就输出最小字典序的欧拉路径

欧拉路径 手写栈
WA8 WA15 TLE28
我就是个弟弟
WA8是因为出入栈顺序的问题，WA15是因为地点直接设置成了1，TLE是因为遍历的是邻接表，所以如果存在2e6个1的自环的情况下时间复杂度会达到$ O(m ^ 2) $
改成用栈删边之后，时间复杂度降低到$ O(m) $

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
vector<Edge> G;
vector<Edge> G_;
vector<int> edges[maxn];
bool vis[maxn * 2];
int in[maxn],out[maxn],beg[maxn];
vector<int> ans;
stack<int> all;
int n,m,s = 0,t = 0,flag = 0,cnt = 0;

void solve(){
	all.push(s);
	mst(beg,0);
	while(!all.empty()){
		int now = all.top();
		if(beg[now] == out[now]){
			ans.push_back(now);
			all.pop();
		}
		else{
			int v = G[edges[now][beg[now]]].to;
			beg[now] ++;
			all.push(v);
			cnt ++;
		}
	}
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
	int u,v;
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		cin>>u>>v;
		G_.push_back(Edge(u,v));
	}
	sort(G_.begin(),G_.end());
	for(int i = 0;i < m;i++){
		G.push_back(G_[i]);
		edges[G_[i].from].push_back(G.size() - 1);
		out[G_[i].from] ++;
		in[G_[i].to] ++;
	}
	for(int i = 1;i <= n;i++){
		if(in[i] == out[i]) continue;
		else if(out[i] - in[i] == 1){
			if(s == 0) s = i;
			else{
				flag = 1;
				break;
			}
		}
		else if(in[i] - out[i] == 1){
			if(t == 0) t = i;
			else{
				flag = 1;
				break;
			}
		}
		else{
			flag = 1;
			break;
		}
	}
	if(s == 0 && t == 0 && flag == 0) {
        for(int i = 1;i <= n;i++) if(out[i] != 0){s = i;break;}
        solve();
    }
	else if(s != 0 && t != 0 && flag == 0) solve();
	else {
		cout<<"What a shame!"<<endl;
		return 0;
	}
	if(cnt != m){
		cout<<"What a shame!"<<endl;
		return 0;
	}
	int len = ans.size();
	for(int i = len - 1;i >= 0;i--) cout<<ans[i]<<" ";
	return 0;
}
D - oydy的征途III

给定一个带权无向图，从第一个点开始，求出到一个序列的点的最短距离

最短路 树链剖分 `
除去树之后多出来的边比较少，所以先把树拿出来求树上距离，再跑出剩下30条边的端点到其他点的最短路
每次询问取经过剩下的边上的端点距离和树上距离
树上距离我直接扒了一棵生成树下来树剖
时间复杂度$ O(30(n + m)logn + nlogn) $

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
struct Node{
	ll l,r;
	ll sum;
}tr[maxn * 5];

struct node{
	ll u;
	ll d;
	node(ll uu,ll dd):u(uu),d(dd){}

	bool operator < (const node& a) const{
		return d > a.d;
	}
};

vector<Edge> G1,G2,G;
vector<ll> edges1[maxn],edges2[maxn];
ll fa[maxn],siz[maxn],dep[maxn],minn[maxn],son[maxn],pos[maxn],top[maxn];
ll dist[65][maxn];
ll mn[maxn],tid = 0,f[maxn];

ll n,m,cnt = 0;
ll from,to;
ll dis;
ll t,nxt,now = 1;

ll tfind(ll x){
	return x == f[x] ? x : (f[x] = tfind(f[x]));
}

void dfs1(ll now,ll pre,ll deep){
	fa[now] = pre;
	siz[now]++;
	dep[now] = deep;
	ll len = edges2[now].size();
	for(ll i = 0;i<len;i++){
		ll v = G2[edges2[now][i]].to;
		if(v == pre) continue;
		minn[v] = G2[edges2[now][i]].dist;
		dfs1(v,now,deep+1);
		siz[now] += siz[v];
		if(son[now] == -1 || siz[son[now]] < siz[v]) son[now] = v;
	}
}

void dfs2(ll now,ll chain){
	pos[now] = tid++;
	top[now] = chain;
	mn[pos[now]] = minn[now];
	ll len = edges2[now].size();
	if(son[now] == -1) return ;
	dfs2(son[now],chain); 
	for(ll i = 0;i<len;i++){
		ll v = G2[edges2[now][i]].to;
		if(v != fa[now] && v != son[now]){
			dfs2(v,v);
		}
	}
}

void build(ll k,ll l,ll r){
	tr[k].l = l;
	tr[k].r = r;
	if(l == r){
		tr[k].sum = mn[l];
		return ;
	}
	ll mid = (l + r)/2;
	build(k<<1,l,mid);
	build(k<<1|1,mid + 1,r);
	tr[k].sum = tr[k<<1].sum+tr[k<<1|1].sum;
}

ll query(ll s,ll t,ll l,ll r,ll k){
	if(s == l&& t == r){
		return tr[k].sum;
	}
	ll mid = (l + r)>>1;
	if(t <= mid) return query(s,t,l,mid,k<<1);
	else if (s > mid) return query(s,t,mid+1,r,k<<1|1);
	else return query(s,mid,l,mid,k<<1)+query(mid + 1,t,mid + 1,r,k<<1|1);
}

ll Query(ll s,ll t){
	ll ans = 0;
	ll chain1 = top[s],chain2 = top[t];
	while(chain1 != chain2){
		if(dep[chain1] < dep[chain2]) swap(chain1,chain2),swap(s,t);
		if(chain1 == 1) ans += query(pos[chain1] + 1,pos[s],1,tid - 1,1);
		else ans += query(pos[chain1],pos[s],1,tid-1,1);
		s = fa[chain1];
		chain1 = top[s];
	}
	if(s == t) return ans;
	if(dep[s] > dep[t]) swap(s,t);
	ans += query(pos[son[s]],pos[t],1,tid - 1,1);
	return ans;
}

void dij(ll s){
	for(ll i = 1;i <= n;i++) dist[cnt][i] = INF;
	bool vis[maxn];
    mst(vis,0);
    priority_queue<node> q;
    q.push(node(s,0));
    dist[cnt][s] = 0;
    while(!q.empty()){
    	node now = q.top();
    	q.pop();
    	ll u = now.u;
    	if(vis[u]) continue;
    	vis[u] = 1;
    	ll len = edges1[u].size();
    	for(ll i = 0;i < len;i++){
    		ll v = G1[edges1[u][i]].to;
    		if(dist[cnt][v] > G1[edges1[u][i]].dist +  dist[cnt][u]){
    			dist[cnt][v] = G1[edges1[u][i]].dist +  dist[cnt][u];
    			q.push(node(v,dist[cnt][v]));
    		}
    	}
    }
    cnt ++;
}

int main(){
	cin>>n>>m;
	for(ll i = 1;i <= n;i++) f[i] = i;
	for(ll i = 1;i <= m;i++){
		cin>>from>>to>>dis;
		ll a = tfind(from),b = tfind(to);
		G1.push_back(Edge(from,to,dis));
		G1.push_back(Edge(to,from,dis));
		edges1[from].push_back(G1.size() - 2);
		edges1[to].push_back(G1.size() - 1);
		if(a != b){
		    G2.push_back(Edge(from,to,dis));
		    G2.push_back(Edge(to,from,dis));
		    edges2[from].push_back(G2.size() - 2);
		    edges2[to].push_back(G2.size() - 1);
		    f[b] = a;
		}
		else {
			G.push_back(Edge(from,to,dis));
		}
	}
	mst(son,-1);
	dfs1(1,0,1);
	dfs2(1,1);
	build(1,1,tid - 1);
	cin>>t;
	ll l = G.size();
	for(ll i = 0;i < l;i++){
		dij(G[i].from);
	}
	ll ans = 0;
	for(ll i = 1;i <= t;i++){
		cin>>nxt;
		ll tans = Query(now,nxt);
		for(ll j = 0;j < l;j++)  tans = min(tans,dist[j][now] + dist[j][nxt]);
		ans += tans;
		now = nxt;
	}
	cout<<ans<<endl;
	return 0;
}
E - 变色龙

给定$ n $个点，$ m $条边，每条边都有颜色，求出从1号点到$ n $号点所需要变换颜色最多的次数

以边代点 拆点
一开始能想到的只有将一条边经过一个点到另外一条边考虑成从一个点到另外一个点，如果颜色相同的两个点的权值就是0，反之为1
但是遇到菊花图的时候空间复杂度是$ O(m^2) $，如不存边的话时间复杂度又会变成$ O(m^2) $
于是看了题解知道要拆点QAQ，用map把空间复杂度降到$ O(m + n) $，跑一遍dijkstra求最短路再除2

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
int n,m;
int cnt = 0;
map<pair<int,int>,int> node;

vector<Edge> G;
vector<int> edges[maxn*10];

void addedge(int u,int v,int w){
	G.push_back(Edge(u,v,w));
	G.push_back(Edge(v,u,w));
	edges[u].push_back(G.size() - 2);
	edges[v].push_back(G.size() - 1);
}

void add(int u,int v,int color){
	pair<int,int> tmp1,tmp2;
	tmp1.first = u;
	tmp1.second = color;
	tmp2.first = v;
	tmp2.second = color;
	if(node[tmp1] == 0) node[tmp1] = ++cnt;
	if(node[tmp2] == 0) node[tmp2] = ++cnt;
	addedge(u,node[tmp1],1);
	addedge(node[tmp1],node[tmp2],0);
	addedge(node[tmp2],v,1);
}

int dij(){
	priority_queue<Node> q;
	bool vis[cnt + 1];
	int dist[cnt + 1];
	mst(vis,0);
	for(int i = 1;i <= cnt;i++) dist[i] = INF;
	dist[1] = 0;
	q.push(Node(1,dist[0]));
	while(!q.empty()){
		Node now = q.top();
		q.pop();
		int u = now.u;
		if(vis[u]) continue;
		vis[u] = 1;
		int len = edges[u].size();
		for(int i = 0;i < len;i++){
			int v = G[edges[u][i]].to;
			if(dist[v] > dist[u] + G[edges[u][i]].dist){
				dist[v] = dist[u] + G[edges[u][i]].dist;
				q.push(Node(v,dist[v]));
			}
		}
	}
	return dist[n] >> 1;
}

int main(){
	//freopen("std.in","r",stdin);
	ios::sync_with_stdio(false); 
	cin.tie(0);
	cin>>n>>m;
	int u,v,color;
	cnt = n;
	for(int i = 1;i <= m;i++){
		cin>>u>>v>>color;
		add(u,v,color);
	}
	cout<<dij()<<endl;
	return 0;
}
F - zh吃饭

给出一个有向图，求经过每个边权后到达某个点集内的点总的最大的边权和

tarjan 缩点
tarjan求强连通分量直接缩点重新建图跑最长路，找了以前写的缩点的代码直接粘上来嘿嘿嘿

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
int n,m,tmp,s,p;
int cnt = 0,sum = 0,top = 0,dfn[maxn],low[maxn],instack[maxn],q[maxn],fa[maxn],dis[maxn];
int dist[maxn];
bool vis[maxn];
int w[maxn];
vector<Edge> G,G2;
vector<int> edges[maxn],edges2[maxn],all;

void Addedge(int u,int v){
	G.push_back(Edge(u,v));
	edges[u].push_back(G.size() - 1);
}

void Addedge2(int u,int v){
	G2.push_back(Edge(u,v));
	edges2[u].push_back(G2.size() - 1);
}

void tarjan(int x){
	cnt ++;
	top ++;
	dfn[x] = low[x] = cnt;
	q[top] = x;
	instack[x] = true;
	int len = edges[x].size();
	for(int i = 0;i < len;i++){
		int v = G[edges[x][i]].to;
		if(dfn[v] == 0){
			tarjan(v);
			low[x] = min(low[x],low[v]);
		}
		else if(instack[v]) low[x] = min(low[x],low[v]);
	}
	if(dfn[x] == low[x]){
		sum++;
		while(q[top + 1] != x){
			int s = q[top];
			top--;
			instack[s] = 0;
			fa[s] = sum;
			dis[sum] += w[s];
		}
	}
}

void spfa(){
	queue<int> q;
	q.push(fa[s]);
	mst(vis,0);
	mst(dist,0);
	dist[fa[s]] = dis[fa[s]];
	vis[fa[s]] = 1;
	while(!q.empty()){
		int now = q.front();
		int len = edges2[now].size();
		q.pop();
		vis[now] = 0;
		for(int i = 0;i < len;i++){
			int v = G2[edges2[now][i]].to;
			if(dist[v] < dist[now] + dis[v]){
				dist[v] = dist[now] + dis[v];
				if(!vis[v]){
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}

int main(){
	int u,v;
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		cin>>u>>v;
		Addedge(u,v);
	}
	for(int i = 1;i <= n;i++) cin>>w[i];
	cin>>s>>p;
    for(int i = 1;i <= p;i++) {
    	cin>>tmp;
    	all.push_back(tmp);
    }
    for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i);
    for(int i = 0;i < m;i++){
    	u = G[i].from;
    	v = G[i].to;
    	if(fa[u] != fa[v]) Addedge2(fa[u],fa[v]);
    }
    spfa();
    int ans = 0;
    for(int i = 0;i < p;i++) ans = max(ans,dist[fa[all[i]]]);
    cout<<ans<<endl;
    return 0;
}


G - hqf吹泡泡

给定$ n $个点，有$ m $ 种连接关系，表示$ u $、$ v $两个点连接所需要的代价是$ w $，要求最少的将所有点连接成$ k $块所需要的代价

最小生成树
本来能1A的一个题结果手太抖了错失一血。。
直接用最小生成树的算法，每连接一次就减去当前块数的数量，然后减到k的时候结束输出答案
时间复杂度$ O(nlogn) $

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
ll n,m,k,tt = 0;
ll cnt;
int fa[maxn],siz[maxn],vis[maxn];
vector<Edge> all;
int u,v,w;
ll ans = 0;

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

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m>>k;
	cnt = n;
	mst(siz,0);
	mst(vis,0);
	for(int i = 1;i <= n;i++) fa[i] = i;
	for(int i = 1;i <= m;i++){
		cin>>u>>v>>w;
		all.push_back(Edge(u,v,w));
	}
	sort(all.begin(),all.end());
	int len = all.size();
	while(cnt != k && tt < len){
		Edge now = all[tt];
		tt++;
		int a = tfind(now.from),b = tfind(now.to);
		if(a == b) continue;
		else{
			if(siz[a] >= siz[b]){
				siz[a] += siz[b];
				ans += now.dist;
				fa[b] = a;
			}
			else{
				siz[b] += siz[a];
				ans += now.dist;
				fa[a] = b;
			}
			cnt --;
		}
	}
	cout<<ans<<endl;
	return 0;
}
H - 毁灭东湖计划

给定一个有向图，求出从1到n的最大流量

网络瘤
网络瘤板题，抄了紫书的EK板子(逃

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
vector<Edge> G;
vector<int> edges[maxn];
ll a[maxn],p[maxn],ans = 0;

void Addedge(int u,int v,ll cap){
	G.push_back(Edge(u,v,cap,0));
	G.push_back(Edge(v,u,0,0));
	edges[u].push_back(G.size() - 2);
	edges[v].push_back(G.size() - 1);
}

ll Maxflow(int s,int t){
	ll res = 0;
	for(;;){
		mst(a,0);
		queue<int> q;
		q.push(s);
		a[s] = INF;
		while(!q.empty()){
			int now = q.front();
			q.pop();
			int len = edges[now].size();
			for(int i = 0;i < len;i++){
				Edge& e = G[edges[now][i]];
				if(!a[e.to] && e.cap > e.flow){
					p[e.to] = edges[now][i];
					a[e.to] = min(a[now], e.cap - e.flow);
					q.push(e.to);
				}
			}
			if(a[t]) break;
		}
		if(!a[t]) break;
		for(int u = t;u != s;u = G[p[u]].from){
			G[p[u]].flow += a[t];
			G[p[u] ^ 1].flow -= a[t];
		}
		res += a[t];
	}
	return res;
}

int main(){
	int u,v,n,m;
	ll c;
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		cin>>u>>v>>c;
		Addedge(u,v,c);
	}
	ans = Maxflow(1,n);
	cout<<ans<<endl;
	return 0;
}
I - cxx仙女下凡

给出一个有向图，求出其中从$ s $到$ t $第$ k $短的路径长度

k短路 A*
k短路模板题，先spfa求出其他点到t最短的路径长度，用A*的估价函数进行估值然后拓展，第k次经过的时候就是第k短路

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

struct node{
	int pos,d,f;
	bool operator < (const node& a) const{
		if(f == a.f) return d > a.d;
		return f > a.f;
	}
};

int n,m,k,s,t;
ll dist[maxn];
vector<Edge> G,G2;
vector<int> edges[maxn],edges2[maxn];

void AddEdge(int u,int v,int w){
	G.push_back(Edge(u,v,w));
	edges[u].push_back(G.size() - 1);
	G2.push_back(Edge(v,u,w));
	edges2[v].push_back(G2.size() - 1);
}

void spfa(int start){
	queue<int> q;
	bool vis[maxn];
	q.push(start);
	mst(vis,0);
	vis[start] = 1;
	for(int i = 1;i <= n;i++) dist[i] = INF;
	dist[start] = 0;
    while(!q.empty()){
    	int now = q.front(),len = edges2[now].size();
    	q.pop();
    	vis[now] = 0;
    	for(int i = 0;i < len;i++){
    		int v = G2[edges2[now][i]].to;
    		if(dist[v] > dist[now] + G2[edges2[now][i]].dist){
    			dist[v] = dist[now] + G2[edges2[now][i]].dist;
    			if(!vis[v]){
    				vis[v] = 1;
    				q.push(v);
    			}
    		}
    	}
    }
}

ll Get_k(){
	if(dist[s] == INF) return -1; 
	priority_queue<node> q;
	node now,nxt;
	now.pos = s;
	now.d = 0;
	now.f = dist[s];
	q.push(now);
	int cnt = 0;
	while(!q.empty()){
		now = q.top();
		q.pop();
		if(now.pos == t) cnt++;
		if(cnt == k) return now.d;
		int len = edges[now.pos].size();
		for(int i = 0 ;i < len;i++){
			int v = G[edges[now.pos][i]].to;
			nxt.d = now.d + G[edges[now.pos][i]].dist;
			nxt.f = nxt.d + dist[v];
			nxt.pos = v;
			q.push(nxt);
		}
	}
	return -1;
}

int main(){
	int u,v;
	ll d;
	cin>>n>>m>>k>>s>>t;
	for(int i = 1;i <= m;i++){
		cin>>u>>v>>d;
		AddEdge(u,v,d);
	}
	spfa(t);
	ll ans = Get_k();
	cout<<ans<<endl;
	return 0;
}
J - cxx守株待兔

给出一个二分图，求最大匹配

匈牙利 网络瘤
把二分图的两边加一个超级源点和一个超级汇点，然后跑一下网络流（
一开始以为EK会被卡就套了Dinic的板子，结果试了一下EK也可以过。。

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
vector<Edge> G;
vector<int> edges[maxn];
int n,s,t,cap;
bool vis[maxn];
int d[maxn],cur[maxn];
ll a[maxn],p[maxn],ans = 0;
int l,r,m;

void Addedge(int u,int v,ll cap){
	G.push_back(Edge(u,v,cap,0));
	G.push_back(Edge(v,u,0,0));
	edges[u].push_back(G.size() - 2);
	edges[v].push_back(G.size() - 1);
}

bool bfs(){
	mst(vis,0);
	queue<int> q;
	q.push(s);
	d[s] = 0;
	vis[s] = 1;
	while(!q.empty()){
		int now = q.front();
		q.pop();
		int len = edges[now].size();
		for(int i = 0;i < len;i++){
			Edge &e = G[edges[now][i]];
			if(!vis[e.to]&&e.cap > e.flow){
				vis[e.to] = 1;
				d[e.to] = d[now] + 1;
				q.push(e.to);
			}
		}
	}
	return vis[t];
}

ll dfs(int x,ll a){
	if(x == t || a == 0) return a;
	ll flow = 0,f;
	int len = edges[x].size();
	for(int i = cur[x];i <len;i++){
		Edge &e = G[edges[x][i]];
		if(d[x] + 1 == d[e.to] && (f = dfs(e.to,min(a,e.cap - e.flow))) > 0){
			e.flow += f;
			G[edges[x][i] ^ 1].flow -= f;
			flow += f;
			a -= f;
			if(a == 0) break;
		}
	}
	return flow;
}

ll Maxflow(){
	int flow = 0;
	while(bfs()){
		mst(cur,0);
		flow += dfs(s,INF);
	}
	return flow;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int u,v;
	cin>>l>>r>>m;
	s = 0,t = l + r + 1;
	for(int i = 1;i <= l;i++) Addedge(s,i,1);
	for(int i = l + 1;i <= l + r;i++) Addedge(i,t,1);
	for(int i = 1;i <= m;i++){
		cin>>u>>v;
		Addedge(u,v + l,1);
	}
	cout<<Maxflow()<<endl;
	return 0;
}
K - cxx承包鱼塘

给出一个带权无向图，求出最多免费k条边后$ s $到$ t $的最短距离

分层图 DP
在dijkstra里面加一个免费这条边的情况下的最短距离，然后类似于动态规划搞一下
时间复杂度$ O((m + n)logn) $

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
int n,m,k,s,t;
int from,to,dis;
ll dist[maxn][30];
bool vis[maxn][30];
vector<Edge> G;
vector<int> edges[maxn];

void Addegde(int u,int v,int d){
	G.push_back(Edge(u,v,d));
	G.push_back(Edge(v,u,d));
	edges[u].push_back(G.size() - 2);
	edges[v].push_back(G.size() - 1);
}

void dij(){
	mst(dist,0x3f3f3f);
	mst(vis,0);
	priority_queue<node> q;
	dist[s][0] = 0;
	q.push(node(s,0,0));
	while(!q.empty()){
		node now = q.top();
		q.pop();
		if(vis[now.u][now.t]) continue;
        vis[now.u][now.t] = 1;
		int len = edges[now.u].size();
		for(int i = 0;i < len;i++){
			int v = G[edges[now.u][i]].to;
			if(dist[v][now.t] > dist[now.u][now.t] + G[edges[now.u][i]].dist){
				dist[v][now.t] = dist[now.u][now.t] + G[edges[now.u][i]].dist;
				q.push(node(v,now.t,dist[v][now.t]));
			}
			if(now.t + 1 <= k){
				if(dist[v][now.t + 1] > dist[now.u][now.t]){
					dist[v][now.t + 1] = dist[now.u][now.t];
					q.push(node(v,now.t + 1,dist[v][now.t + 1]));
				}
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m>>k>>s>>t;
	for(int i = 1;i <= m;i++){
		cin>>from>>to>>dis;
		Addegde(from,to,dis);
	}
	dij();
	cout<<dist[t][k]<<endl;
	return 0;
}
L - cxx的压岁钱

给定n个电视所需要花费的代价，以及选取某几个电视就可以得到的利润，求出最大的利润

最大权闭合子图 网络流
抽象一下，就是选取某一个结点，那么它的后继也要被选取
看到题目的时候满脸网络流，但是不知道建模是怎么建的emmm
建模的就是将选取的后继的这一边的容量设为无穷大，源点连接的所需要选取的容量为对应利润，后面汇点连接的容量为对应的代价
跑出最大流，然后用$ \sum c$减去最大流

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
vector<Edge> G;
vector<int> edges[maxn];
int n,m,s,t,cap;
bool vis[maxn];
int d[maxn],cur[maxn];
ll a[maxn],p[maxn],ans = 0;

void Addedge(int u,int v,ll cap){
	G.push_back(Edge(u,v,cap,0));
	G.push_back(Edge(v,u,0,0));
	edges[u].push_back(G.size() - 2);
	edges[v].push_back(G.size() - 1);
}

bool bfs(){
	mst(vis,0);
	queue<int> q;
	q.push(s);
	d[s] = 0;
	vis[s] = 1;
	while(!q.empty()){
		int now = q.front();
		q.pop();
		int len = edges[now].size();
		for(int i = 0;i < len;i++){
			Edge &e = G[edges[now][i]];
			if(!vis[e.to]&&e.cap > e.flow){
				vis[e.to] = 1;
				d[e.to] = d[now] + 1;
				q.push(e.to);
			}
		}
	}
	return vis[t];
}

ll dfs(int x,ll a){
	if(x == t || a == 0) return a;
	ll flow = 0,f;
	int len = edges[x].size();
	for(int i = cur[x];i <len;i++){
		Edge &e = G[edges[x][i]];
		if(d[x] + 1 == d[e.to] && (f = dfs(e.to,min(a,e.cap - e.flow))) > 0){
			e.flow += f;
			G[edges[x][i] ^ 1].flow -= f;
			flow += f;
			a -= f;
			if(a == 0) break;
		}
	}
	return flow;
}

ll Maxflow(){
	int flow = 0;
	while(bfs()){
		mst(cur,0);
		flow += dfs(s,INF);
	}
	return flow;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	s = 0;
	t = m + n + 1;
	for(int i = 1;i <= m;i++){
		cin>>cap;
		Addedge(n + i,t,cap);
	}
	int sum = 0;
	for(int i = 1;i <= n;i++){
		int a,k;
		cin>>a>>k;
		sum += a;
		Addedge(s,i,a);
		for(int j = 0;j < k;j++){
			int v;
			cin>>v;
			Addedge(i,v + n,INF);
		}
	}
	cout<<sum - Maxflow()<<endl;
	return 0;
}
M - 洁姐姐带我找工作

给出每两个公司的给出的offer数量关系，求出最少的offer数

dfs 并查集 拓扑排序

既然是图论，一开始想到的是建一个有向图表示大于小于关系，但是等于关系想不清楚
当时晚上放题的时候还想到了差分约束emmmm
然后想到用并查集将等于的点缩在一个点上，但是排序对应点的权值的处理有点问题
后来想到的是并查集 + 拓扑排序，但是拓扑排序排不出来（我是辣鸡
那么把大于的建图反向过来，这样方便从1开始处理权值，然后每次选取入度为0的点开始dfs
求出每个点对应的深度就是权值，然后每次递归到某一层如果权值已经不为0了就选择最大的一个深度作为权值
最后把权值全部加起来就是答案

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
int fa[1007],siz[1007],in[1007],vis[1007],w[1007];
int n,m,op,u,v,ans = 0,maxx = 1,flag = 0;

vector<Edge> G,G1;
vector<int> edges[1007],all;
queue<int> q;

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

void addedge(int u,int v){
	G1.push_back(Edge(u,v));
	edges[u].push_back(G1.size() - 1);
}

void dfs(int x,int dep){
	int len = edges[x].size();
	w[x] = max(w[x],dep + 1);
	for(int i = 0;i < len;i++){
		int v = G1[edges[x][i]].to;
		if(vis[v] == 1){
			flag = 1;
			continue;
		}
		vis[v] = 1;
		dfs(v,dep + 1);
		vis[v] = 0;
	}
}

int main(){
	mst(vis,0);
	mst(in,0);
	cin>>n>>m;
	for(int i = 1;i <= n;i++) fa[i] = i,siz[i] = 1;
	for(int i = 1;i <= m;i++){
		cin>>op>>u>>v;
		if(op == 1) G.push_back(Edge(u,v));
		else if(op == 2) G.push_back(Edge(v,u));
		else {
			int a = tfind(u),b = tfind(v);
			fa[b] = a;
			siz[a] += siz[b];
		}
	}
	int len = G.size();
	for(int i = 0;i < len;i++){
		int u = G[i].from,v = G[i].to;
		u = tfind(u),v = tfind(v);
		if(u == v){
			cout<<-1<<endl;
			return 0;
		}
		in[u] ++;
		addedge(v,u);
	}
	for(int i = 1;i <= n;i++){
		if(w[tfind(i)] == 0 && in[tfind(i)] == 0) dfs(tfind(i),0);
	}
	for(int i = 1;i <= n;i++){
		ans += w[tfind(i)];
		if(w[tfind(i)] == 0) flag = 1;
	}
	if(flag){
		cout<<-1<<endl;
		return 0;
	}
	cout<<ans<<endl;
	return 0;
}
N - 洁姐姐带我上分

jjjj一次能带$ k $个人上段位，每次jjjj不在的情况下每队cp都不能在一起，jjjj可以随意地上段位或者下段位，求出最少的让所有人都到高段位的代价

DAG DP 状态压缩
这题也是康题解做的
用二进制整数表示当前某个段位的状态，然后筛出合法的数据，按照条件得到合法转移条件连边
最后跑一遍最短路。。

合法状态：末位为0的同时不能有一对cp的位置同时为1
合法转移：1的个数少于等于$ k $ 、状态转移的变量末位是1、同时两个转移状态之间的最大值减去状态变化值是两个转移状态的最小值

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
struct Node{
	int u,d;
	Node(int uu,int dd):u(uu),d(dd){}
	bool operator < (const Node& a) const{
		return d > a.d;
	}
};

int n,m,k,maxx;
vector<pair<int,int>> all;
vector<int> statu;
vector<Edge> G;
vector<int> edges[maxn * 10];

void Addedge(int from,int to,int dist){
	G.push_back(Edge(from,to,dist));
	G.push_back(Edge(to,from,dist));	
	edges[from].push_back(G.size() - 2);
	edges[to].push_back(G.size() - 1);
}

bool check(int now){
	int now_ = maxx - now,len = all.size();
	bool flag1 = 0,flag2 = 0;
	for(int i = 0;i < len;i++){
		if((now & 1) == 0 && ((now >> all[i].x) & 1) == 1 && ((now >> all[i].y) & 1 == 1)) flag1 = 1;
		if((now_ & 1) == 0 && ((now_ >> all[i].x) & 1) == 1 && ((now_ >> all[i].y) & 1) == 1) flag2 = 1;
	}
	if(flag1 == 1 || flag2 == 1) return false;
	return true;
}

int get(int x){
	int res = 0;
	while(x){
		if(x & 1) res ++;
		x >>= 1;
	}
	return res;
}

int dij(){
	int dist[maxx];
	bool vis[maxx];
	priority_queue<Node> q;
	mst(vis,0);
	for(int i = 0;i <= maxx;i++) dist[i] = INF;
	dist[maxx] = 0;
    q.push(Node(maxx,0));
    while(!q.empty()){
    	Node now = q.top();
    	q.pop();
    	int u = now.u;
    	if(vis[u]) continue;
    	vis[u] = 1;
    	int len = edges[u].size();
    	for(int i = 0;i < len;i++){
    		Edge &e = G[edges[u][i]];
    		if(dist[e.to] > dist[u] + e.dist){
    			dist[e.to] = dist[u] + e.dist;
    			q.push(Node(e.to,dist[e.to]));
    		}
    	}
    }
    return dist[0];
}

int main(){
	cin>>n>>m>>k;
	pair<int,int> tmp;
	for(int i = 1;i <= m;i++){
		cin>>tmp.x>>tmp.y;
		all.push_back(tmp);
	}
	maxx = (1 << (n + 1)) - 1;
	for(int i = 0;i <= maxx;i++){
		if(check(i)) statu.push_back(i);
	}
	int len = statu.size();
	for(int i = 0;i < len;i++){
		for(int j = i + 1;j < len;j++){
			int det = statu[i] ^ statu[j];
			int cnt = get(det);
			if(max(statu[i],statu[j]) - det == min(statu[i],statu[j]) && cnt <= k && det & 1 == 1){
				Addedge(statu[i],statu[j],cnt);
			}
		}
	}
	int ans = dij();
	if(ans == INF) cout<<"mole"<<endl;
	else cout<<ans<<endl;
	return 0;
}

O - 洁姐姐带学画画

给出n个点，已经它们在三维空间中的坐标，求出生成树，并且每条线段的连接的两个点的高度差之和比上水平距离之和最小

最小生成树 prim 牛顿迭代 01分数规划
用一个表达式表示一个最小生成树，权值总和为
$$
x_1a_1 + x_2a_2 + … +x_na_n
$$
$x_i$表示选取或者不选取
令得到的答案为$ans$
那么有
$$
\frac {\sum x_ih_i}{\sum x_id_i} >= ans \
移项，有 \sum x_ih_i >= ans\sum x_id_i \
展开，x_1(h_1 - ansd_1) + x_2(h_1 - ans * d_2) + … + x_n(h_n - ansd_n) >= 0
$$
可以进行二分判断得到的ans是否使得最小生成树为0即可，
除了使用二分，还可以使用牛顿迭代法更新答案直到$x >= xx$，也就对应二分上面式子为0的时候

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
int n;
struct Node{
	double x,y,z;
};

Node nodes[maxn];
double cost[maxn][maxn],len[maxn][maxn];
double M[maxn][maxn];

double dis(Node a,Node b){
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void get(){
	for(int i = 0;i < n;i++){
		for(int j = i + 1;j < n;j++){
			cost[i][j] = cost[j][i] = fabs(nodes[i].z - nodes[j].z);
			len[i][j] = len[j][i] = dis(nodes[i],nodes[j]);
		}
	}
}

double low[maxn];
bool vis[maxn];
int pre[maxn];

double prime(){
	for(int i = 0;i <n;i++){
		vis[i] = 0;
		low[i] = M[0][i];
		pre[i] = 0;
	}
	vis[0] = 1;
	double sumcost = 0,sumlen = 0;
	for(int i = 1;i < n;i++){
		double min = INF;
		int nxt = 0;
		for(int j = 0;j < n;j++){
			if(!vis[j] && min > low[j]){
				nxt = j;
				min = low[j];
			}
		}
		vis[nxt] = 1;
		sumcost += cost[pre[nxt]][nxt];
		sumlen += len[pre[nxt]][nxt];
		for(int j = 0;j < n;j++){
			if(!vis[j] && low[j] > M[nxt][j]){
				low[j] = M[nxt][j];
				pre[j] = nxt;
			}
		}
	}
	return sumcost / sumlen;
}

void Mapp(double x){
	for(int i = 0;i < n;i++){
		for(int j = i + 1;j < n;j++){
			M[i][j] = M[j][i] = cost[i][j] - x * len[i][j];
		}
	}
}

int main(){
	cin>>n;
	for(int i = 0;i < n;i++){
		cin>>nodes[i].x>>nodes[i].y>>nodes[i].z;
	}
	get();
	double sumc = 0,suml = 0,xx;
	for(int i = 1;i < n;i++) sumc += cost[0][i],suml += len[0][i];
	double x = sumc / suml;
    while(1){
    	xx = x;
    	Mapp(xx);
    	x = prime();
    	if(fabs(xx - x) < eps) break;
    }
    printf("%.3lf\n",x);
    return 0;
}