分类目录归档：图论

CSP 202009-3 点亮数字人生

拓扑排序，另外这道题字符串处理太多了，麻烦死了。这种第三题全都是大模拟。非常麻烦。

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

struct node {
string type;
int input;
string signals[10];
bool value;
};

void topoSortDegreeMinus(int id, vector<int> &inDegree, const vector<vector<int>> &edges) {
if (inDegree[id] != 0)return;
inDegree[id] = -1;
vector<int> storage;
for (int i = 0; i < edges[id].size(); i++) {
inDegree[edges[id][i]]--;
if (inDegree[edges[id][i]] == 0)
storage.push_back(i);
}
for (int i = 0; i < storage.size(); i++) {
topoSortDegreeMinus(storage[i], inDegree, edges);
}
}

bool checkCircle(int n, unordered_map<string, node> &nodeMap) { //Topological sort
vector<int> inDegree;
inDegree.resize(n+1);
vector<vector<int>> edges;
edges.resize(n+1);

for (int i = 1; i <= n; i++) {
string nodeID = "O" + to_string(i);
const node &curNode = nodeMap[nodeID];
for (int j = 0; j < curNode.input; j++) {
if (curNode.signals[j][0] == 'O') {
inDegree[i]++;
int edgeStart = strtol(&curNode.signals[j].c_str()[1], NULL, 10);
edges[edgeStart].push_back(i);
}
}
}

bool flag = false;
do {
flag = false;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
topoSortDegreeMinus(i, inDegree, edges);
flag = true;
}
}
} while (flag);

for (int i = 1; i <= n; i++) {
if (inDegree[i] > 0)
return true;
}
return false;
}

bool calculateLogicDFS(unordered_map<string, node> &nodeMap,
unordered_map<string, bool> &visited, string ID) {
node &curNode = nodeMap[ID];
if (visited[ID])return curNode.value;
visited[ID] = true;
if (ID[0] == 'I')return curNode.value;
if (curNode.type == "NOT") {
calculateLogicDFS(nodeMap, visited, curNode.signals[0]);
curNode.value=!nodeMap[curNode.signals[0]].value;
} else if (curNode.type == "AND") {
curNode.value = true;
for(int i=0;i<curNode.input;i++){
calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
curNode.value &= nodeMap[curNode.signals[i]].value;
if(!curNode.value)break;
}
} else if (curNode.type == "OR") {
curNode.value = false;
for(int i=0;i<curNode.input;i++){
calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
curNode.value |= nodeMap[curNode.signals[i]].value;
if(curNode.value)break;
}
} else if (curNode.type == "XOR") {
curNode.value = false;
for(int i=0;i<curNode.input;i++){
calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
curNode.value ^= nodeMap[curNode.signals[i]].value;
}
} else if (curNode.type == "NAND") {
curNode.value = true;
for(int i=0;i<curNode.input;i++){
calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
curNode.value &= nodeMap[curNode.signals[i]].value;
if(!curNode.value)break;
}
curNode.value=!curNode.value;
} else if (curNode.type == "NOR") {
curNode.value = false;
for(int i=0;i<curNode.input;i++){
calculateLogicDFS(nodeMap, visited, curNode.signals[i]);
curNode.value |= nodeMap[curNode.signals[i]].value;
if(curNode.value)break;
}
curNode.value=!curNode.value;
}
return curNode.value;
}

void calculateLogic(unordered_map<string, node> &nodeMap) {
unordered_map<string, bool> visited;
for(auto iter=nodeMap.begin();iter!=nodeMap.end();iter++){
if(!visited[iter->first])
calculateLogicDFS(nodeMap,visited,iter->first);
}
}

void solve() {
// Read Part 1
int m, n;
cin >> m >> n;
unordered_map<string, node> nodeMap;
for (int i = 1; i <= n; i++) {
node curNode;
cin >> curNode.type >> curNode.input;
for (int j = 0; j < curNode.input; j++) {
cin >> curNode.signals[j];
}
nodeMap["O" + to_string(i)] = curNode;
}

// Check Circle: Topological Sort
bool haveCircle = checkCircle(n, nodeMap);

// Read Part 2
int s;
cin >> s;
vector<vector<int>> inputs;
inputs.resize(s);
for (int i = 0; i < s; i++) {
inputs[i].push_back(m);
int t;
for (int j = 0; j < m; j++) {
cin >> t;
inputs[i].push_back(t);
}
}
vector<vector<int>> outputs;
outputs.resize(s);
for (int i = 0; i < s; i++) {
int k;
cin >> k;
outputs[i].push_back(k);
int t;
for (int j = 1; j <= k; j++) {
cin >> t;
outputs[i].push_back(t);
}
}

if (haveCircle) {
cout << "LOOP\n";
return;
}
for (int i = 0; i < s; i++) {
for (int j = 1; j <= m; j++) {
node tmpNode;
tmpNode.value = inputs[i][j];
nodeMap["I" + to_string(j)] = tmpNode;
}
calculateLogic(nodeMap);
for(int j=1;j<=outputs[i][0];j++){
cout<<nodeMap["O"+to_string(outputs[i][j])].value<<" ";
}
cout<<"\n";
}
}

int main() {
ios::sync_with_stdio(false);
int q;
cin >> q;
while (q--)
solve();
}

Openjudge BJUTACM 19g系列代码

发表评论

题目链接：
http://bjutacm.openjudge.cn/lianxi/?page=2

继续阅读 →

洛谷 P3381 【模板】最小费用最大流

发表评论

参考链接：https://www.cnblogs.com/widerg/p/9394929.html

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

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 100005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m, s, t;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始，奇数号顶点存储反向边
int to[eN << 1], nxt[eN << 1], value[eN << 1], cost[eN << 1];
int head[vN], dis[vN], minV[vN];
int preID[eN << 1], preNode[eN << 1];
bool inqueue[vN];
inline void createEdge(int u, int v, int w, int c) {
to[++ePtr] = v;
value[ePtr] = w;
cost[ePtr] = c;
nxt[ePtr] = head[u];
head[u] = ePtr;
}
bool SPFA(int s, int t) {
queue<int> q;
memset(dis, 0x7f, sizeof(dis));
memset(inqueue, false, sizeof(inqueue));
memset(preID, -1, sizeof(preID));
memset(preNode, -1, sizeof(preNode));
memset(minV, 0x7f, sizeof(minV));
dis[s] = 0;
inqueue[s] = true;
q.push(s);
while (!q.empty()) {
int x = q.front();
q.pop();
inqueue[x] = false;
for (int i = head[x]; ~i; i = nxt[i]) {
int dest = to[i];
if (dis[dest] > dis[x] + cost[i] && value[i]) {
dis[dest] = dis[x] + cost[i];
minV[dest] = min(minV[x], value[i]);
preID[dest] = i;
preNode[dest] = x;
if (!inqueue[dest]) {
inqueue[dest] = true;
q.push(dest);
}
}
}
}
return dis[t] != INF;
}
void MinCostMaxFlow(int s, int t, int& maxflow, int& mincost) {
while (SPFA(s, t)) {
for (int i = t; i != s; i = preNode[i]) {
value[preID[i]] -= minV[t];
value[preID[i] ^ 1] += minV[t];
}
maxflow += minV[t];
mincost += minV[t] * dis[t];
}
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++) {
int u, v, w, f;
scanf("%d%d%d%d", &u, &v, &w, &f);
createEdge(u, v, w, f);
createEdge(v, u, 0, -f);//第0号边被占用，这条语句为反向边留下空间
}
int maxflow = 0, mincost = 0;
MinCostMaxFlow(s, t, maxflow, mincost);
printf("%d %d\n", maxflow, mincost);
}

洛谷 P3376 【模板】网络最大流

发表评论

参考链接：https://www.cnblogs.com/widerg/p/9387909.html

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

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 100005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m, s, t;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始，奇数号顶点存储反向边
int to[eN<<1], nxt[eN<<1], value[eN<<1];
int head[vN], dis[vN];
inline void createEdge(int u, int v, int w) {
to[++ePtr] = v;
value[ePtr] = w;
nxt[ePtr] = head[u];
head[u] = ePtr;
}
bool bfs(int s, int t) {
queue<int> q;
memset(dis, 0x7f, sizeof(dis));
dis[s] = 0;
q.push(s);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; ~i; i = nxt[i]) {
int dest = to[i];
if (dis[dest] == INF && value[i] != 0) {
dis[dest] = dis[x] + 1;
q.push(dest);
}
}
}
return dis[t] != INF;
}
int dfs(int x, int t, int maxflow) {
if (x == t)return maxflow;
int ans = 0;
for (int i = head[x]; ~i; i = nxt[i]) {
int dest = to[i];
if (dis[dest] != dis[x] + 1 || value[i] == 0 || ans >= maxflow)continue;
int f = dfs(dest, t, min(value[i], maxflow - ans));
value[i] -= f;
value[i ^ 1] += f;
ans += f;
}
return ans;
}
int dinic(int s, int t) {
int ans = 0;
while (bfs(s, t))ans += dfs(s, t, INF);
return ans;
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
createEdge(u, v, w);
createEdge(v, u, 0);//第0号边被占用，这条语句为下一个边留下空间
}
printf("%d", dinic(s, t));
}

洛谷 P3386 【模板】二分图匹配

发表评论

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

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<list>
#include<cmath>
#include<queue>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int n, m, e;
vector<int> edges[2005];
bool visited[2005];
int match[2005];
bool biFind(int node) {
if (visited[node])return false;
visited[node] = true;
for (int i = 0; i < edges[node].size(); i++) {
if (!match[edges[node][i]] || biFind(match[edges[node][i]])) {
match[node] = edges[node][i];
match[edges[node][i]] = node;
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> e;
for (int i = 1; i <= e; i++) {
int u, v;
cin >> u >> v;
if (u > n || v > m)continue;
edges[u].push_back(v + n);
edges[v + n].push_back(u);
}
int cnter = 0;
for (int i = 1; i <= n; i++) {
memset(visited, false, sizeof(visited));
if (biFind(i))cnter++;
}
cout << cnter;
}

计蒜客 Random Access Iterator

发表评论

原题链接：https://nanti.jisuanke.com/t/41392
竟然做出来一道这么复杂的概率+DFS+逆元题，开心到爆炸，特此发题解一篇^v^

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

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#define MOD 1000000007
#define ll long long
using namespace std;
int n;
int MDep;
vector<int> edges[1000005];
bool visited[1000005];
ll quickpow(ll a, ll b) {
if (b == 0)return 1;
ll re = quickpow(a, b / 2) % MOD;
re = (re * re) % MOD;
if (b % 2 == 1)re *= a % MOD;
return re % MOD;
}
inline ll inv(ll x) {
return quickpow(x, MOD - 2) % MOD;
}
inline ll chance1(ll TotNode) {
ll ch = (inv(TotNode)) % MOD;
return ch;
}
inline ll chance2(ll onceCh,ll TotNode) {
ll onceNonch = (1ll-onceCh+MOD) % MOD;
ll nonch = quickpow(onceNonch, TotNode);
ll fin = (1ll - nonch + MOD) % MOD;
return fin;
}
int dfsMaxDep(int node) {
int maxDep = 1;
bool hasChild = false;
visited[node] = true;
for (int i = 0; i < edges[node].size(); i++) {
if (visited[edges[node][i]])continue;
hasChild = true;
maxDep = max(maxDep, dfsMaxDep(edges[node][i]) + 1);
}
return maxDep;
}
ll dfsChance(int depth,int node){
if (depth == MDep)return 1;
ll ch = 0,sCh=chance1(node==1?edges[node].size(): edges[node].size()-1);
visited[node] = true;
for (int i = 0; i < edges[node].size(); i++) {
if (visited[edges[node][i]])continue;
ll CurCH = dfsChance(depth + 1, edges[node][i]);
if (CurCH) {
ch += (CurCH * sCh) % MOD;
ch %= MOD;
}
}
return chance2(ch, node == 1 ? edges[node].size() : edges[node].size() - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
}
MDep = dfsMaxDep(1);
memset(visited, false, sizeof(visited));
ll ch = dfsChance(1, 1);
cout << ch;
}

洛谷 P1113 杂务

发表评论

这题本来就是个拓扑排序，搞了半天竟然搞不出来，想了半天。。
一开始的想法是：搞拓扑排序，一轮一轮的扫描，每一轮出一个最大时间，把最大时间相加就好了，后来发现全WA，为什么呢？因为同一轮里出来的任务其实有可能是不互相依赖的。比如任务1时间需要10；任务2时间需要5；任务3需要在任务1之后，任务4需要在任务2之后。如果一轮一轮的扫描，那么必须10秒之后同时开始做任务3/4。而实际情况则应该是任务2，5个时间作完之后就可以做任务4了。根据失误我又想着反向建图，用DFS递归解决，对每个结点（及其之前节点）找其最大的所用时间，写出来AC了（对于本题，杂务 k(k>1)的准备工作只可能在杂务 1 至 k-1 中，如果没有这个要求，反向建图就很好）。但是其实我想多了。直接一开始的拓扑排序，顺着推就可以了。
DFS版：

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

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,times[10005],inDegree[10005],f[10005];
vector<int> edges[10005];
vector<int> curTasks;
int dfs(int node){
if(f[node]!=0)return f[node];
if(edges[node].size()==0)return f[node]=times[node];
int maxT=0;
for(int i=0;i<edges[node].size();i++){
maxT=max(maxT,dfs(edges[node][i]));
}
return f[node]=maxT+times[node];
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
int v;
cin>>v>>times[i];
while(1){
cin>>v;
if(v==0)break;
edges[i].push_back(v);
inDegree[v]++;
}
}
int maxTime=0;
for(int i=1;i<=n;i++){
if(inDegree[i]==0)maxTime=max(maxTime,dfs(i));
}
cout<<maxTime;
}

正常版：

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

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,times[10005],inDegree[10005],allTimes[10005];
vector<int> edges[10005];
int sumTime=0;
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
int v;
cin>>v>>times[i];
while(1){
cin>>v;
if(v==0)break;
edges[v].push_back(i);
inDegree[i]++;
}
}
int maxT=0;
for(int i=1;i<=n;i++)if(inDegree[i]==0){
allTimes[i]+=times[i];
for(int j=0;j<edges[i].size();j++){
allTimes[edges[i][j]]=max(allTimes[edges[i][j]],allTimes[i]);
inDegree[edges[i][j]]--;
}
inDegree[i]--;
maxT=max(maxT,allTimes[i]);
}
cout<<maxT;
}

洛谷 P1144 最短路计数

发表评论

自己一开始写了个，才60分，效率不高，后来看了题解。
参考题解：https://www.luogu.org/blog/user43513/luo-gu-p1144-zui-duan-lu-ji-shuo-ti-xie
60分代码：

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

#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
edgePtr++;
nxt[edgePtr]=fst[s];
v[edgePtr]=e;
fst[s]=edgePtr;
}
void SP(){
memset(visited,false,sizeof(visited));
memset(dis,0x7f,sizeof(dis));
queue<int> q,qd;
q.push(1);qd.push(0);
while(!q.empty()){
int node=q.front(),dist=qd.front();
q.pop();qd.pop();
if(visited[node])continue;
visited[node]=true;
dis[node]=dist;
for(int e=fst[node];e!=-1;e=nxt[e]){
if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
dis[v[e]]=dis[node]+1;
q.push(v[e]);qd.push(dis[v[e]]);
}
}
}
}
void DFS(int node,int dist){
if(dist!=dis[node])return;
cnter[node]++;
cnter[node]%=MOD;
for(int e=fst[node];e!=-1;e=nxt[e]){
if(visited[e])continue;
visited[e]=true;
DFS(v[e],dist+1);
visited[e]=false;
}
}
int main(){
memset(fst,-1,sizeof(fst));
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if(x==y)continue;
edgePush(x,y);
edgePush(y,x);
}
SP();
memset(visited,false,sizeof(visited));
DFS(1,0);
for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}

100分的：

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

#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
edgePtr++;
nxt[edgePtr]=fst[s];
v[edgePtr]=e;
fst[s]=edgePtr;
}
void SP(){
memset(visited,false,sizeof(visited));
memset(dis,0x7f,sizeof(dis));
queue<int> q,qd;
q.push(1);qd.push(0);
cnter[1]=1;
while(!q.empty()){
int node=q.front(),dist=qd.front();
q.pop();qd.pop();
if(visited[node])continue;
visited[node]=true;
dis[node]=dist;
for(int e=fst[node];e!=-1;e=nxt[e]){
if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
dis[v[e]]=dis[node]+1;
q.push(v[e]);qd.push(dis[v[e]]);
cnter[v[e]]+=cnter[node];
cnter[v[e]]%=MOD;
}else if(dis[v[e]]==dis[node]+1){
cnter[v[e]]+=cnter[node];
cnter[v[e]]%=MOD;
}
}
}
}
int main(){
memset(fst,-1,sizeof(fst));
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if(x==y)continue;
edgePush(x,y);
edgePush(y,x);
}
SP();
for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}

洛谷 P1346 电车

发表评论

基本上是裸的最短路，是第一个不用扳道岔的边长就是0，后面的需要扳道岔的长度就是1。然后愉快的套一个Dijkstra板子就可以了。

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

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n,a,b;
struct edge{
int v,w;
edge(int vv,int ww){v=vv;w=ww;}
bool operator < (const edge& e2) const{
return w>e2.w;
}
};
vector<edge> edges[105];
priority_queue<edge> pq;
bool visited[105];
int dis[105];
int main(){
ios::sync_with_stdio(false);
cin>>n>>a>>b;
for(int i=1;i<=n;i++){
int t;
cin>>t;
for(int j=1;j<=t;j++){
int v;
cin>>v;
if(j==1)edges[i].push_back(edge(v,0));
else edges[i].push_back(edge(v,1));
}
}
//Dijkstra
memset(dis,0x7f,sizeof(dis));
pq.push(edge(a,0));
while(!pq.empty()){
edge cur=pq.top();
pq.pop();
if(visited[cur.v])continue;
visited[cur.v]=true;
dis[cur.v]=cur.w;
for(int i=0;i<edges[cur.v].size();i++){
if(!visited[edges[cur.v][i].v]&&dis[edges[cur.v][i].v]>dis[cur.v]+edges[cur.v][i].w){
dis[edges[cur.v][i].v]=dis[cur.v]+edges[cur.v][i].w;
pq.push(edge(edges[cur.v][i].v,dis[edges[cur.v][i].v]));
}
}
}
if(dis[b]!=0x7f7f7f7f)cout<<dis[b];
else cout<<-1;
}

洛谷 P1991 无线通讯网

发表评论

这道题很显然能够看出，只需找出与卫星电话数相等的联通块数，然后取联通块里的最大边就可以了。但是我想不出来怎么好写。
看过题解之后，经题解提醒“树的性质：删掉n条边一定出现n+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

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int s, p;
struct edge {
int u, v;
double w;
bool operator < (const edge& e2) const {
return w < e2.w;
}
}edges[125000];
struct point {
int x, y;
}points[505];
int father[505];
int _find(int x) {
if (father[x] == 0)return x;
return father[x] = _find(father[x]);
}
bool _union(int x, int y) {
x = _find(x); y = _find(y);
if (x == y)return false;
father[x] = y;
return true;
}
inline double dis(int x1, int y1, int x2, int y2) {
return sqrt((double)((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)));
}
int main() {
//ios::sync_with_stdio(false);
cin >> s >> p;
for (int i = 1; i <= p; i++) {
cin >> points[i].x >> points[i].y;
}
int ePtr = 0;
for (int i = 1; i <= p; i++) {
for (int j = i + 1; j <= p; j++) {
ePtr++;
edges[ePtr].u = i;
edges[ePtr].v = j;
edges[ePtr].w = dis(points[i].x, points[i].y, points[j].x, points[j].y);
}
}
sort(edges + 1, edges + ePtr + 1);
int cnter = 0;
for (int i = 1; i <= ePtr; i++) {
if (_union(edges[i].u, edges[i].v)) {
cnter++;
}
if (cnter == p - 1 - (s - 1)) {
printf("%.2lf", edges[i].w);
break;
}
}
}

杰克部落

梦想本不会发光，发光的是追梦的你

分类目录归档：图论

CSP 202009-3 点亮数字人生

Openjudge BJUTACM 19g系列代码

洛谷 P3381 【模板】最小费用最大流

洛谷 P3376 【模板】网络最大流

洛谷 P3386 【模板】二分图匹配

计蒜客 Random Access Iterator

洛谷 P1113 杂务

洛谷 P1144 最短路计数

洛谷 P1346 电车

洛谷 P1991 无线通讯网

2024 年 11 月
一	二	三	四	五	六	日
				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