2017 UESTC 图论专题题解
题目链接:2017 UESTC Training for Graph Theory
Content
[CDOJ 1636] A - 梦后楼台高锁,酒醒帘幕低垂
[CDOJ 1633] B - 去年春恨却来时,落花人独立,微雨燕双飞
[CDOJ 1634] C - 记得小苹初见,两重心字罗衣
[CDOJ 1635] D - 琵琶弦上说相思,当时明月在,曾照彩云归
[CDOJ 1638] E - 红藕香残玉簟秋,轻解罗裳,独上兰舟。
[CDOJ 1639] F - 云中谁寄锦书来?雁字回时,月满西楼。
[CDOJ 1640] G - 花自飘零水自流,一种相思,两处闲愁。
[CDOJ 1641] H - 此情无计可消除,才下眉头,却上心头。
[CDOJ 1642] I - 老当益壮, 宁移白首之心?
[CDOJ 1646] J - 穷且益坚, 不坠青云之志。
[CDOJ 1647] K - 酌贪泉而觉爽, 处涸辙以犹欢。
[CDOJ 1636] A - 梦后楼台高锁,酒醒帘幕低垂
Problem
给一个带正边权的无向图,路径的权值为路径上所有边的最大值与最小值之差,问从 1 到 n 的所有路径的最小权值。
1≤n≤200, n−1≤m≤1000, 1≤u,v≤n, 1≤w≤1000000
Solution
想到二分答案,那如果要判断某个答案值可不可行,需要从某条边开始,按边权从小到大依次将比它大的边加入图中,直至 1 和 n 联通或者边权差值超出答案。
那好像不需要二分答案了,直接枚举最小边,寻找可使 1 和 n 联通的最小的最大边就行了,并查集维护。
复杂度 O(mlgm + m^2)
Code
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct re {
int x, y, z;
} a[1010];
inline bool cmp(re a, re b) {return a.z < b.z;}
int i, n, m, j, res, nn, ans, p, q;
int f[210];
int find(int x) {
if (f[x] == x) return x;
f[x] = find(f[x]);
return f[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (i = 1; i <= m; i++)
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
sort(a + 1, a + m + 1, cmp);
ans = 1000000000;
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++) f[j] = j;
nn = n - 1;
res = 1000000000;
for (j = i; j <= m; j++)
{
p = find(a[j].x); q = find(a[j].y);
if (p == q) continue;
f[q] = p;
p = find(1); q = find(n);
if (p == q)
{
res = a[j].z - a[i].z;
break;
}
}
ans = min(ans, res);
}
if (ans == 1000000000) puts("-1");
else printf("%d\n", ans);
return 0;
}
Note
[HDU 1598]find the most comfortable road
[CDOJ 1633] B - 去年春恨却来时,落花人独立,微雨燕双飞
Problem
给你一个大小为 n(1≤n≤2000) 的集合 S,集合里有 n 个互不相同正整数 (1≤ai≤50000) 。有 q(1≤q≤10000) 个询问,每次询问是否能选择 S 中的一些数字(同一个数字可以选择多次,也可以任何数字都不选),使它们相加的和为 m(0≤m≤1000000000) 。
Solution
把最小的 ai 挑出来作为模数 r,以 r 建立剩余系,这样就只要找出模 r 为 x 的最小的数是多少(把这个设为 d[x]),那么如果有 ai 的话,那么就可以做 y = (x + ai) % r; d[y] = min(d[y], d[x] + ai)
这样的更新操作,这样其实就是一个最短路模型,共 r 个点,有 n * r 条边。跑一下最短路就行。。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX=1e9+10;
const int R=5010;
int d[R];
bool g[R];
int a[20100];
int i, k, r, Q, j, y, n;
priority_queue <pair<int, int>> q;
void dij(int x)
{
int tot=0, mi, i;
q.push(make_pair(-d[x], x));
while (tot < r && !q.empty())
{
mi = q.top().second;
q.pop();
if (g[mi]) continue;
g[mi] = 1;
tot++;
for (i = 1; i <= n; i++)
{
y = (mi + a[i]) % r;
if (!g[y] && d[y] - d[mi] > a[i])
{
d[y] = d[mi] + a[i];
q.push(make_pair(-d[y], y));
}
}
}
return;
}
int main()
{
scanf("%d", &n);
for (i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
r = a[1];
for (i = 1; i <= r; i++) d[i] = MAX;
d[r] = 0;
dij(r);
scanf("%d", &Q);
while (Q--)
{
scanf("%d", &k);
puts( (k >= d[k % r]) ? "YES" : "NO" );
}
return 0;
}
Note
非常智障,想到了要用剩余做,却想不到怎么往图论上靠。。
[CDOJ 1634] C - 记得小苹初见,两重心字罗衣
Problem
平面上有 n 个点,将每个点染成红色或者蓝色,使得每一行和每一列的红点蓝点之差不超过 1。
n≤200000, 1≤x,y≤200000
Solution
因为要将每条横线和竖线上的点尽可能均分成两类。
所以考虑染色,构造连边然后红蓝交替着染路径上的点。
从最终的结果来推想,一条横线上的点的红蓝差 <= 1,那么这条横线上一定可以让红蓝点两两配对,然后连边,而且最后横线上最多多出来一个点。(竖线也是相同的道理)
那么就按顺序染一下试试看?
对于每一条横线,从左到右,按顺序选取未选择的两点,连一条边。
对于每一条竖线,从上到下,按顺序选取未选择的两点,连一条边。
例如: O O O O O O O O O O O 连边后: O---O | | O | | | | O-------O (注意这里并不交叉) | | | | O | | | O---O O | O--O
这样的连线方案,一定可以保证最终平面上有一堆链(可能还有孤立的点),因为每个点只能在纵向或者横向两个方向连边,而且在竖直方向上最多只能连出去一条边,横向最多也只能连出去一条边,不可能出现 “+” 或者 “┬” 这种样子的点。
因为对于链,红蓝交替染色必然可行,对于孤立点随便染(注意孤立点在每条横线或者竖线上最多有一个),这样染完后,每条横线或者竖线上红蓝差必然是 <= 1 的,所以这样的染色方案是可行的。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200010;
const int M=N<<2;
struct re {
int x, y, z;
} a[N];
int i, tot, n;
int st[N];
int nex[M], v[M];
bool g[N], f[N];
void add(int x, int y)
{
v[++tot] = y;
nex[tot] = st[x];
st[x] = tot;
}
bool cmp(re a, re b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
void connect()
{
sort(a + 1, a + n + 1, cmp);
int x=1, y, j;
while (x < n)
{
y = x;
while (a[y + 1].x == a[y].x) y++;
for (j = x + 1; j <= y; j += 2)
{
add(a[j - 1].z, a[j].z);
add(a[j].z, a[j - 1].z);
}
x = y + 1;
}
}
void color(int x, int w)
{
f[x] = w;
g[x] = 1;
for (int i = st[x]; i; i = nex[i])
if (!g[v[i]]) color(v[i], w ^ 1);
}
int main()
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].x, &a[i].y);
a[i].z = i;
}
a[n + 1].x = a[n + 1].y = a[n + 1].z = -1;
connect();
for (i = 1; i <= n; i++) swap(a[i].x, a[i].y);
connect();
for (i = 1; i <= n; i++)
{
if (!g[i]) color(i, 1);
putchar(f[i] ? 'b' : 'r');
}
puts("");
return 0;
}
Note
[Codeforces 547D]Mike and Fish
[CDOJ 1635] D - 琵琶弦上说相思,当时明月在,曾照彩云归
Problem
给你 n 个仅由小写字母组成的字符串,请你找出一种字典序,使得这 n 个字符串在这种字典序下是从小到大排列的
1≤n≤1000, 1≤len(s)≤200
Solution
对于所有的字符串,可以对相邻的字符串进行逐位比较,得出字符间的大小关系,由此应该能得到一张拓扑关系图,如果图存在环,则输出 -1。否则的话,因为字符比较少,所以我直接 dfs 求出所有字母间的先后关系,然后直接从 a 到 z 暴力枚举答案。
有种特殊情况是两个字符串,后者是前者的前缀而且前者比后者长,这种情况一定是不合法的,输出 -1,被坑了很久的一种情况。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
const int N=40;
const int M=200010;
char s[2][210];
bool g[N], cx[N][N], flag;
int a[100];
int st[N], nex[M], b[M];
int i, n, x, y, j, k, tot, len;
void add(int x, int y)
{
x -= 96; y -= 96;
cx[x][y] = 1;
b[++tot] = y;
nex[tot] = st[x];
st[x] = tot;
}
void dfs(int x)
{
g[x] = 1;
for (int i = st[x]; i; i = nex[i])
if (!g[b[i]])
{
dfs(b[i]);
for (int j = 1; j <= 26; j++)
if (cx[b[i]][j]) cx[x][j] = 1;
}
}
int main()
{
scanf("%d", &n);
scanf("%s", &s[0]);
for (i = 2; i <= n; i++)
{
x = i & 1;
y = x ^ 1;
scanf("%s", &s[y]);
len = min(strlen(s[x]), strlen(s[y]));
for (j = 0; j < len; j++)
if (s[x][j] != s[y][j])
{ add(s[x][j], s[y][j]); break; }
if (j == len && strlen(s[x]) > strlen(s[y]))
{ puts("-1"); return 0; }
}
for (i = 1; i <= 26; i++)
if (!g[i]) dfs(i);
for (i = 1; i <= 26; i++)
for (j = 1; j <= 26; j++)
if (cx[i][j] && cx[j][i])
{
puts("-1");
return 0;
}
memset(g, 0, sizeof(g));
for (i = 1; i <= 26; i++)
{
for (j = 1; j <= 26; j++)
if (!g[j])
{
flag = true;
for (k = 1; k <= 26; k++)
if (!g[k] && cx[k][j])
{ flag = 0; break; }
if (flag)
{
g[j] = 1;
a[i] = j;
break;
}
}
if (flag == false)
{ puts("-1"); return 0; }
}
for (i = 1; i <= 26; i++) putchar(a[i] + 96);
puts("");
return 0;
}
Note
[POJ 1364]King
[CDOJ 1638] E - 红藕香残玉簟秋,轻解罗裳,独上兰舟。
Problem
n(1≤n≤100000) 个学生,m(1≤m≤100000) 条信息 (u, v, w),表示 score[v] + w <= score[u]
(0≤w≤100),求 score[i] | i=1..n 可能的最大值和最小值
Solution
差分约束系统
根据不等式 score[v] + w <= score[u]
建图,同时设置一个超级源作为最小值,根据 min - score[x] <= 0
不等式将所有点连接起来,那么只要从这个超级源出发,做一遍 spfa 就能求出下限了
然后将不等式移项 score[u] - w >= score[v]
,再次建图(相当于上张图反向),然后设置一个超级源作为最大值,连接所有点,然后做 spfa 可求出上限
因为这道题点数比较多,所以在 spfa 中通过入队列的次数来判负环会 TLE
所以我事先 dfs 判断了是否存在负环,因为还可能存在零环,所以在 dfs 的时候还加了一个深度标记,如果搜索到了一个仍还在栈中且深度不一样的点,则说明存在负环
Code
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
using namespace std;
const int N=110000;
const int M=2000100;
const int INF=0x3fffffff+100;
int n, m, tot;
int d1[N];//, cnt[N];
int d2[N];
int deep[N];
bool inq[N], ins[N];
int st[N], v[M], nex[M], w[M];
int a[M>>1], b[M>>1], c[M>>1];
void no()
{
puts("-1");
exit(0);
}
void init()
{
tot = 0;
memset(st, -1, (n + 5) * sizeof(st[0]));
}
void add(int x, int y, int z)
{
v[tot] = y;
w[tot] = z;
nex[tot] = st[x];
st[x] = tot++;
}
void dfs(int x, int dee)
{
inq[x] = ins[x] = 1;
deep[x] = dee;
for(int i = st[x]; i != -1; i = nex[i])
{
if (ins[v[i]] && dee != deep[v[i]]) no();
if (!inq[v[i]]) dfs(v[i], dee + w[i]);
}
ins[x] = 0;
}
void circle()
{
memset(inq, 0, (n + 5) * sizeof(inq[0]));
memset(ins, 0, (n + 5) * sizeof(ins[0]));
dfs(n + 1, 0);
}
void spfa(int* dd, int initial)
{
queue<int> q;
int a, b;
memset(inq, 0, (n + 5) * sizeof(inq[0]));
//memset(cnt, 0, (n + 5) * sizeof(cnt[0]));
for(int i = 0; i <= n; i++) dd[i] = INF;
dd[n + 1] = initial;
inq[n + 1] = 1;
q.push(n + 1);
//cnt[n + 1]++;
while (!q.empty())
{
a = q.front(); q.pop();
//if (cnt[a] > n + 1) no();
inq[a] = 0;
for(int i = st[a]; i != -1; i = nex[i])
{
b = v[i];
if(dd[b] > dd[a] + w[i])
{
dd[b] = dd[a] + w[i];
if(inq[b] == 0)
{
inq[b] = 1;
q.push(b);
//cnt[b]++;
}
}
}
}
}
int main()
{
int i;
scanf("%d%d", &n, &m);
init();
for (i = 1; i <= n; i++) add(n + 1, i, 0); // max - i >= 0
for (i = 1; i <= m; i++)
{
scanf("%d%d%d", &a[i], &b[i], &c[i]);
if (a[i] == b[i])
{
if (c[i] != 0) no();
else continue;
}
// a[i] - b[i] >= c[i]
// a[i] - c[i] >= b[i]
add(a[i], b[i], -c[i]);
}
circle();
spfa(d1, 100);
init();
for (i = 1; i <= n; i++) add(n + 1, i, 0); // min - i <= 0
for (i = 1; i <= m; i++)
{
if (a[i] == b[i])
{
if (c[i] != 0) no();
else continue;
}
// b[i] - a[i] <= -c[i]
// b[i] + c[i] <= a[i]
// (-b[i]) - c[i] >= (-a[i]) 化为最短路
add(b[i], a[i], -c[i]);
}
circle();
spfa(d2, 0);
for (i = 1; i <= n; i++)
{
d2[i] = -d2[i];
if (d1[i] < 0 || d1[i] > 100 || d2[i] < 0 || d2[i] > 100) no();
}
for (i = 1; i <= n; i++)
printf("%d %d\n", d2[i], d1[i]);
return 0;
}
[CDOJ 1639] F - 云中谁寄锦书来?雁字回时,月满西楼。
Problem
n 个点 m 条边的无向图,节点编号为 0 到 n−1,有 k 个点为安全屋
劫犯们从 0 出发,要到其中一个安全屋(任意一个)
每当劫犯到达一个节点,警察立刻封锁与该点相连的边,对于当前点警察最多能够封锁与其相连的 d 条边
求在最坏情况下,劫犯能到达安全屋的最短时间
1≤n≤100000,1≤m≤1000000,0≤k≤n,0≤d≤m,0≤u,v<n,0≤w≤10000
Solution
看了题解写的,是 dijkstra 的改版
感觉题解已经讲得非常清楚了,题解原文:
该题为dijkstra算法的拓展 由于求最坏情况下的最短路,对于每个点,显然最优的前d条边不能走 对于边u->v,必然要先得到v到出口的最坏情况下的最短路 才能得到u经过该边再到出口的最坏情况下的最短路,也就是该边对于u的价值 所以要从出口往回考虑 令f[i]表示i到出口的最坏情况下的最短路 同dijkstra算法一样,每个点i可以分为f[i]已确定的和f[i]未确定的 初始时自然是对于每个出口x,f[x]=0已确定 对于f[v]已确定的点v,将边权为w的边u->v以f[v]+w为关键字加入小根堆中 对于每个点i还要记录cnt[i]=k,表示到i后,i连出的最优的前k条边已被封锁 每次取出堆顶对应的边u->v(若f[u]已确定直接弹出) 则该边为u连出的(除已被封锁的边外)最优的边 若cnt[u]<d,该边必然会被封锁,那么将cnt[u]加1,弹出堆顶 若cnt[u]=d,那么可以确定f[u]=f[v]+w,再用u更新连向u的边,弹出堆顶 重复这一过程直到确定f[0]的值,该值即为答案
这里的堆通过边来维护最近的点,每次松弛都是挑选当前最近的点,也就是对于每一个点,去松弛它的距离一定是从小到大的,小的先松弛,大的后松弛,这样就能挑出最优的 k 种情况封锁掉。
Code
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=100020;
const int M=1000020<<1;
priority_queue<pair<int, int>> q;
int v[M], w[M], nex[M];
int st[N], d[N], cnt[N];
int tot, i, kk, lim, n, m;
char ch;
void read(int &x)
{
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar());
for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 - 48 + ch;
}
void add(int x, int y, int z)
{
v[++tot] = y;
w[tot] = z;
nex[tot] = st[x];
st[x] = tot;
}
void add_edge(int x)
{
for (int i = st[x]; i != -1; i = nex[i])
{
int y = v[i];
if (d[y] == -1)
q.push(make_pair(- d[x] - w[i], y));
}
}
void dij()
{
int x;
pair<int, int> p;
while (d[0] == -1 && !q.empty())
{
p = q.top(); q.pop();
x = p.second;
if (d[x] != -1) continue;
cnt[x]++;
if (cnt[x] == lim + 1)
{
d[x] = - p.first;
add_edge(x);
}
}
}
int main()
{
read(n); read(m); read(kk); read(lim);
int xx, yy, ww;
memset(st, -1, sizeof(st[0]) * (n + 5));
memset(d, -1, sizeof(d[0]) * (n + 5));
for (i = 1; i <= m; i++)
{
read(xx); read(yy); read(ww);
add(xx, yy, ww);
add(yy, xx, ww);
}
for (i = 1; i <= kk; i++)
{
read(xx);
d[xx] = 0;
add_edge(xx);
cnt[xx] = lim + 1;
}
dij();
printf("%d\n", d[0]);
return 0;
}
[CDOJ 1640] G - 花自飘零水自流,一种相思,两处闲愁。
Problem
有向图,从 1 出发,回到 1,允许在有向边上逆行一次,最多能遍历多少个点
1≤n,m≤100000,1≤x,y≤n
Solution
我的想法是,先缩点,点权就是分量大小,重新建图,那么 1 所在的这个分量的点都会被遍历,然后对所有从 1 连出去的点 xjb DP,但是 WA 了。。
看了题解,意思是,对于剩下的点,如果存在 u->v 这条边,如果逆着走过它的话,那么额外遍历的点数就是 1->v 能遍历的最多的点加上 u->1 能遍历的最多的点
怎么算这个东西?因为已经缩完了点,所以就不会存在环的问题,这整个就是一个拓扑图,做两次 dp 就能预处理出来,之前想多了,分太多种情况了。
然后就只要枚举边,然后两边加一加算一下,选个最大的就行了。
然而就是 A 不掉。。 数组边界开小了,这个错误隐藏得非常隐蔽。。mdzz
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define fi first
#define se second
const int N=100010;
const int M=100010;
int dfn[N], low[N], s[N], b[N], cnt[N], g[N], deg[N], degr[N];
int st[N], str[N], f[N], fr[N];
int v[M], vr[M], nex[M], nexr[M];
bool ins[N];
int fltot, tot, totr, i, n, m, ind, size, core, flag;
pair <int, int> edge[M];
void add(int x, int y)
{
v[++tot] = y;
nex[tot] = st[x];
st[x] = tot;
}
void addr(int x, int y)
{
vr[++totr] = y;
nexr[totr] = str[x];
str[x] = totr;
}
void tarjan(int x)
{
int i, j;
dfn[x] = low[x] = ++ind;
ins[x] = 1;
s[++size] = x; //É趨xµÄʱ¼ä´ÁºÍlow³õÖµ
for (i = st[x]; i; i = nex[i])
{
j = v[i];
if (!dfn[j])
{
tarjan(j);
low[x] = min(low[x], low[j]);
}
else if (ins[j] && dfn[j] < low[x]) low[x] = dfn[j];
}
if (dfn[x] == low[x])
{
fltot++;
do {
j = s[size--];
ins[j] = false;
b[j] = fltot;
cnt[fltot]++;
} while (j != x);
}
}
void dfs(int x)
{
int y;
g[x] = 1;
for (int i = str[x]; i; i = nexr[i])
{
y = vr[i];
if (!g[y]) dfs(y);
if (f[y] > 0)
f[x] = max(f[x], f[y] + cnt[x]);
}
}
void dfs2(int x)
{
int y;
g[x] = 1;
for (int i = st[x]; i; i = nex[i])
{
y = v[i];
if (!g[y]) dfs2(y);
if (fr[y] > 0)
fr[x] = max(fr[x], fr[y] + cnt[x]);
}
}
int main()
{
freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (i = 1; i <= m; i++)
{
scanf("%d%d", &edge[i].fi, &edge[i].se);
if (edge[i].fi != edge[i].se)
add(edge[i].fi, edge[i].se);
}
for (i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
tot = totr = 0;
core = b[1];
memset(st, 0, sizeof(st[0]) * (fltot + 5));
for (i = 1; i <= m; i++)
{
int x = b[edge[i].fi];
int y = b[edge[i].se];
if (x != y)
{ add(x, y); deg[y]++;
addr(y, x); degr[x]++; }
}
f[core] = 1;
g[core] = 1;
for (i = 1; i <= fltot; i++)
if (degr[i] == 0) dfs(i); // core->x
memset(g, 0, sizeof(g[0]) * (fltot + 5));
fr[core] = 1;
g[core] = 1;
for (i = 1; i <= fltot; i++)
if (deg[i] == 0) dfs2(i); // x->core
int ans = cnt[core];
for (i = 1; i <= m; i++)
{
int y = b[edge[i].fi];
int x = b[edge[i].se]; // core <- y->x <- core
if (x != y)
{
if (f[x] > 0) x = f[x] - 1; // core->x
else x = -10000000;
if (fr[y] > 0) y = fr[y] - 1; //y->core
else y = -10000000;
ans = max(ans, x + y + cnt[core]);
}
}
printf("%d\n", ans);
return 0;
}
[CDOJ 1641] H - 此情无计可消除,才下眉头,却上心头。
Problem
n 项的数列 A1~An,每一项的值为 0 / 1
可以花 Cij 的费用询问数列中第 i 项到第 j 项的异或和
至少要花多少费用才能知道数列中每一项的具体值
1≤n≤1000,1≤Cij≤1000000
Solution
因为这个异或和满足区间加减法:
[a, b] ^ [b + 1, c] = [a, c]
[a, b] ^ [c + 1, b] = [a, c]
这样区间之间的=就有了某种传递性,这个传递性和图上的连通性是类似的,就好比 a 和 b 连通,b 和 c 连通,那么 a 和 c 就连通了。
因为上述式子无法直接转成图那样子,所以就考虑分隔线
+-+-+-+-+-+-+-----+-+ |1|2|3|4|5|6|.....|n| +-+-+-+-+-+-+-----+-+ 0 1 2 3 4 5 6 n-1 n
这样的话分隔线之间的连通性就相当于对应区间异或和是否可求
Cij 可以计算出分隔线 i 和分隔线 j+1 之间的异或和,相当于给 (i, j+1) 连一条边
最终目标呢,要使得每一项都可求,那就相当于是 (i, i+1) 连通,等价于所有点连通, 那就太简单啦,裸的最小生成树!
Code
#include<cstdio>
#include<algorithm>
using namespace std;
struct re {
int x, y, z;
} a[1000010];
int tot, x, i, j, n, f[1010], rest, p, q, ans;
char ch;
void read(int &x)
{
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar());
for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 - 48 + ch;
}
bool cmp(re a, re b) { return a.z < b.z; }
int find(int x)
{
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
int main()
{
read(n);
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++)
{
read(x);
a[++tot].x = i - 1;
a[tot].y = j;
a[tot].z = x;
}
sort(a + 1, a + tot + 1, cmp);
for (i = 0; i <= n; i++) f[i] = i;
rest = n;
for (i = 1; i <= tot && rest > 0; i++)
{
p = find(a[i].x);
q = find(a[i].y);
if (p == q) continue;
f[q] = p;
ans += a[i].z;
rest--;
}
printf("%d\n", ans);
return 0;
}
[CDOJ 1642] I - 老当益壮, 宁移白首之心?
Problem
请构造一个 01 串,使其满足以下条件:
环状(即首尾相连),每一位取值为 0 或 1,长度是 2n,对于每个(2n 个)位置,从其开始沿逆时针方向的连续的 n 位 01 串(包括自己)构成的数均不相同,即 0 到 2n−1 中的数各出现一次
Solution
打一发暴力,找了找一个规律,发现每次把满足条件的最小的 01 串展开成 2n 个数之后,最后几个数的二进制形式都是这样的:
11110..0 11100..0 11000..0 10000..0
前面一堆 1 后面一堆 0,1 逐渐减少,0 逐渐增多。。并不会证,然后我就用这个性质 dfs 了一波,搜索根本就没有回溯,直接秒出,check 了一下是对的,就 AC 了。。时间复杂度大概只有 O(2^n),后面就改了一个非递归版的。
Code
#include<cstdio>
#include<cstdlib>
using namespace std;
const int T=100010;
bool g[T];
int a[T], n, tot, mask, lim, left, x, y;
// tot 100000000
// mask 011111111
int main()
{
scanf("%d", &n);
tot = 1 << n;
left = 1 << (n - 1);
mask = left - 1;
a[0] = 0; a[1] = 1;
g[0] = g[1] = 1;
int base = 0;
for (int i = 1; i <= n; i++)
{
base = (base >> 1) | left;
a[tot - i] = base;
g[base] = 1;
}
lim = tot - n - 1;
for (int i = 2; i <= lim; i++)
{
x = (a[i - 1] & mask) << 1;
if (g[x]) x |= 1;
a[i] = x;
g[x] = 1;
}
for (int i = 0; i < tot; i++)
putchar((a[i] & left) ? '1' : '0');
puts("");
return 0;
}
Note
[CDOJ 1646] J - 穷且益坚, 不坠青云之志。
Problem
求一个有 n 个元素的数列,满足任意连续 p 个数的和不小于 s,任意连续 q 个数的和不大于 t
1≤n,p,q≤500, 1≤s,t≤100000
Solution
转化为前缀和,就有一堆不等式啦,然后和 E 一样搞一个差分约束,不过不用求两次,求一次就行了,但还是要搞一个超级源
Code
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2010;
const int M=20010;
const int INF=1000000010;
int q[1000010], cnt[N];
int st[N], nex[M], b[M], c[M];
int d[N];
bool g[N];
int n, P, Q, S, T, tot;
void add(int x, int y, int z)
{ // x + z <= y
b[++tot] = y;
c[tot] = z;
nex[tot] = st[x];
st[x] = tot;
}
bool spfa(int x)
{
int i, j, h, t=0;
for (i = 1; i <= n + 2; i++) d[i] = -INF;
q[++t] = x;
h = d[x] = 0;
cnt[x] = 1;
g[x] = 1;
while (h != t)
{
x = q[++h];
g[x] = 0;
for (j = st[x]; j; j = nex[j])
if (d[x] + c[j] > d[b[j]])
{
d[b[j]] = d[x] + c[j];
if (!g[b[j]])
{
cnt[b[j]]++;
if (cnt[b[j]] > n + 2) return 0;
q[++t] = b[j];
g[b[j]] = 1;
}
}
}
return 1;
}
int main()
{
scanf("%d%d%d%d%d", &n, &P, &Q, &S, &T);
for (int i = 1; i <= n + 1; i++) add(n + 2, i, 0);
// x + z <= y
// s[p + i] - s[i] >= s
// s[i] + s <= s[p + i]
// s[q + i] - s[i] <= t
// s[q + i] - t <= s[i]
T = -T;
add(n + 1, P, S); // s[0] + s <= s[p]
add(Q, n + 1, T);
for (int i = 1; i <= n - P; i++)
add(i, i + P, S);
for (int i = 1; i <= n - Q; i++)
add(i + Q, i, T);
if (spfa(n + 2))
{
puts("Yes");
printf("%d ", d[1]);
for (int i = 2; i <= n; i++) printf("%d ", d[i] - d[i - 1]);
puts("");
}
else puts("No");
return 0;
}
[CDOJ 1647] K - 穷且益坚, 不坠青云之志。
Problem
首行两个整数 n,m(1≤n≤20,1≤m≤100000).
接下来 m 行,每行包括两个01串(长度为 n)和一个整数si,wi,ti,(1≤ti≤1000000000),表示 si 变为 wi 需要 ti 的时间
现在给你初始的 01 串,其长度为 n,并且元素全为 0(即 00…000…0),问你至少需要多长的时间变成全为 1(即11…111…1)
Solution
把 01 串按照其十进制大小映射到整数集上,就转化成最短路模型。。然后就是一道水题。。
Code
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int M=100010;
const int N=M<<1;
const long long INF=((ll)1<<62)-10;
int st[N], nex[M], v[M];
ll w[M], dd[N];
int a2b[N], b2a[2100000];
bool g[N];
int i, x, y, z, vn, n, m, tot;
char s1[100], s2[100];
priority_queue <pair<ll, int>> q;
void add(int x, int y, int z)
{
v[++tot] = y;
w[tot] = z;
nex[tot] = st[x];
st[x] = tot;
}
int dec(char* s)
{
int len=strlen(s), res=0;
for (int i = 0; i < len; i++)
res = (res << 1) | (s[i] - 48);
return res;
}
int lsh(int x)
{
if (b2a[x] == 0)
{
b2a[x] = ++vn;
a2b[vn] = x;
}
return b2a[x];
}
void dij(int x)
{
int tot=0, i, j, y;
q.push(make_pair(0, x));
// memset(g, false, sizeof(g));
for (i = 1; i <= vn; i++) dd[i] = INF;
dd[x] = 0;
while (tot < vn && !q.empty())
{
x = q.top().second;
q.pop();
if (g[x]) continue;
g[x] = 1;
tot++;
for (j = st[x]; j; j = nex[j])
{
y = v[j];
if (!g[y] && dd[y] - dd[x] > w[j])
{
dd[y] = dd[x] + w[j];
q.push(make_pair(-dd[y], v[j]));
}
}
}
return;
}
int main()
{
scanf("%d%d", &n, &m);
for (i = 1; i <= m; i++)
{
scanf("%s%s%d", s1, s2, &z);
x = dec(s1); y = dec(s2);
if (x == y) continue;
x = lsh(x); y = lsh(y);
add(x, y, z);
}
int eend = (1 << n) - 1;
if (b2a[eend] != 0 && b2a[0] != 0)
{
dij(b2a[0]);
if (dd[b2a[eend]] == INF) puts("-1");
else printf("%lld\n", dd[b2a[eend]]);
} else puts("-1");
return 0;
}