19暑假训练2-X

这里是占位符

POJ3169 Layout SPFA 差分约束

将不等式问题转化为图论问题。

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 <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int maxn = 1e4 + 10;
typedef long long ll;
ll dist[maxn];
typedef pair<int,long long> pii;
vector<pii> G[maxn];
int n,ml,md;
bool fail = 0;
bool in[maxn];
int out[maxn];
void spfa() {
queue<int> q;
for(int i = 1; i <= n; ++i)
dist[i] = 2e9;
dist[1] = 0;
q.push(1);
while(q.size()) {
int u = q.front(); q.pop();
in[u] = 0;
++out[u];
if(out[u] > n) {
fail = 1;
return;
}
for(int i = 0; i < G[u].size(); ++i) {
int v = G[u][i].first;
ll w = G[u][i].second;
if(dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if(!in[v]) {
q.push(v);
in[v] = 1;
}
}
}
}
}
int main() {
cin>>n>>ml>>md;
for(int i = 1; i <= ml; ++i) {
int u,v,w;
cin>>u>>v>>w;
G[u].push_back({v,w});
}
for(int i = 1; i <= md; ++i) {
int u,v,w;
cin>>u>>v>>w;
G[v].push_back({u,-w});
}
spfa();
if(dist[n] == 2e9) {
puts("-2");
} else if(fail) puts("-1");
else cout<<dist[n];
}

CF1189D1 思维

给出一棵树,在这棵树上有这样的操作:选择两个叶节点,将连接他们的路径上的边全部加上某个实数 。

问能否在这棵树的任意边上构造出任意的权值。

一开始可能会想到lca之类的,但实际上如果一个点只连了两条边,那么这两条边无论怎么操作权值都是一同变化的,所以构造不出这两边权值不同的情况。所以只要找是否存在度数=2的顶点就行了。

CF1187D 思维

构建一个顶点为n(<=1000)的图,要求边数为素数,每个顶点度数为素数,且无重边和自环。

很显然在[n,n + n / 2]范围里一定有一个素数,所以边数最少是第一个>=n的素数,然后先连成一个环,如果还剩下边就在i -> n/2+i里连。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
bool isp(int n) {
for(int i = 2; i * i <= n; ++i)
if(n % i == 0) return 0;
return 1;
}
int main() {
int n;
cin>>n;
int m = n;
while(!isp(m)) ++m;
cout<<m<<endl;
for(int i = 1; i < n; ++i) {
cout<<i<<" "<<i + 1<<endl;
}
cout<<n<<" 1\n";
for(int i = 1; i <= m - n; ++i) {
cout<<i<<" "<<n / 2 + i<<endl;
}
}

HDU3499 最短路变形

就是最短路,但是可以任选一条边打半价,不能不打,问这种情况下的最短路。

dist[u][0/1]为起点到u是否打过折的最短距离。

dist[v][0]=min(dist[u][0]+edge_w(u,v))

dist[v][1]=min(dis[u][1]+edge_w(u,v),dist[u][0]+edge_w(u,v)/2)

dist[end][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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
ll dist[maxn][2];
typedef pair<int,long long> pii;
vector<pii> G[maxn];
int n,m;
bool vis[maxn][2];
struct st {
int u,st;
ll w;
};
bool operator>(const st &a,const st&b) {
return a.w > b.w;
}
void dij(int start) {
for(int i = 1; i <= n; ++i)
dist[i][0] = dist[i][1] = 1e18,vis[i][0] = vis[i][1] = 0;
dist[start][0] = dist[start][1] = 0;
priority_queue<st,vector<st>,greater<st> > q;
q.push({start,0,0});
while(q.size()) {
int u = q.top().u,t = q.top().st;
q.pop();
if(vis[u][t]) continue;
vis[u][t] = 1;
for(int i = 0; i < G[u].size(); ++i) {
int v = G[u][i].first;
ll w = G[u][i].second;
if(!t && dist[u][t] + w < dist[v][0]) {
dist[v][0] = dist[u][t] + w;
q.push({v,0,dist[v][0]});
}
if(dist[u][t] + (t ? w : w / 2) < dist[v][1]) {
dist[v][1] = dist[u][t] + (t ? w : w / 2);
q.push({v,1,dist[v][1]});
}
}
}
}
int main() {
while(~scanf("%d%d",&n,&m)) {
map<string,int> p;
int cnt = 0;
for(int i = 1; i <= n; ++i)
G[i].clear();
for(int i = 1; i <= m; ++i) {
string u,v;
ll w;
cin>>u>>v>>w;
if(!p[u]) p[u] = ++cnt;
if(!p[v]) p[v] = ++cnt;
G[p[u]].push_back({p[v],w});
//G[p[v]].push_back({p[u],w});
}
string a,b; cin>>a>>b; if(!p[a]) p[a] = ++cnt;
if(!p[b]) p[b] = ++cnt;
int st = p[a],ed = p[b];
dij(st);
if(dist[ed][1] == 1e18) {
puts("-1");
} else {
printf("%lld\n",dist[ed][1]);
}
}
}