World_Devastator

1305

/*好题，别看它只是标为“简单”

（重点）为什么第二次必须要用树形dp求直径？

1
/  \
2      3
/   \     \
4      5     6
/       / \    / \
7       8   9  10  11

（强调）有负权边时，求直径用树形dp
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Edge{
int v, e, nxt;
}E[N << 1];
int n, m, point, last_point, sum, ans, tot = 1; //用到了成对变换找父节点，所以tot初始值为1
int hd[N], dis[N], len[N << 1];
inline void add(int u, int v, int e){
E[++tot] = (Edge){v, e, hd[u]}, hd[u] = tot;
}
void dfs(int u, int fath){ //两次搜索求直径
dis[u] = dis[fath] + 1;
if (dis[u] > dis[point]) point = u;
for (int i = hd[u]; i; i = E[i].nxt)
if (E[i].v != fath)
len[E[i].v] = i, dfs(E[i].v, u);
}
inline int calc(int x, int y){ //修改路径权值
int tmp = 0;
while (x != y){
tmp += E[len[x]].e;
E[len[x]].e = E[len[x] ^ 1].e = -1;
x = E[len[x] ^ 1].v; //反向边的v就是它的父节点
}
return tmp;
}
inline void dp(int u, int fath){ //树形dp求直径
for (int i = hd[u]; i; i = E[i].nxt){
int v = E[i].v;
if (v == fath) continue;
dp(v, u);
sum = max(sum, dis[u] + dis[v] + E[i].e);
dis[u] = max(dis[u], dis[v] + E[i].e);
}
}
int main(){
scanf("%d%d", &n, &m);
ans = 2 * (n - 1);
for (int i = 1; i < n; ++i){
int u, v;
scanf("%d%d", &u, &v);
}

dfs(1, 0); last_point = point;
dfs(point, 0);
ans -= calc(point, last_point) - 1;

if (m == 2){
memset(dis, 0, sizeof dis);
dp(1, 0);
ans -= sum - 1;
}

printf("%d\n", ans);
return 0;
}


/*这题也就看着吓人

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005, inf = 0x3f3f3f3f, mod = INT_MAX;
int n, m; ll ans = 1;
int s[N][N], dis[N], p[N], vis[N];
inline bool comp(int i, int j){
return dis[i] < dis[j];
}
inline void Dijkstra(){ //最短路，裸的Dijkstra
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
for (int i = 1; i <= n; ++i){
int u = 0;
for (int j = 1; j <= n; ++j)
if (!vis[j] && dis[j] < dis[u]) u = j;
vis[u] = 1;
for (int v = 1; v <= n; ++v)
if (s[u][v] != inf && dis[u] + s[u][v] < dis[v])
dis[v] = dis[u] + s[u][v];
}
}
inline void Work(){
for (int i = 1; i <= n; ++i) p[i] = i;
sort(p + 1, p + n + 1, comp); //从近到远确定
for (int i = 2; i <= n; ++i){
int cnt = 0;
for (int j = 1; j < i; ++j)
if (dis[p[j]] + s[p[j]][p[i]] == dis[p[i]]) ++cnt; //满足条件
ans = ans * cnt % mod;
}
}
int main(){
scanf("%d%d", &n, &m);
memset(s, 0x3f, sizeof s);
for (int i = 1; i <= m; ++i){
int u, v, e;
scanf("%d%d%d", &u, &v, &e);
s[u][v] = s[v][u] = min(s[u][v], e);
}
Dijkstra();
Work();
printf("%d", ans);
return 0;
}



/*嗯，这道题应该可以算作一类题的解题思路，最优比率生成树。

*/
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 1005, inf = 0x3f3f3f3f;
const db eps = 1e-5;
struct Node{ int x, y, z;}p[N];
struct Edge{ db c, w;}s[N][N];
int n, vis[N];
db dis[N];
inline db dist(Node a, Node b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
inline bool check(db mid){ //这里的图是完全图，所以用prim比Kruskal更优
memset(vis, 0, sizeof vis);
for (int i = 0; i <= n; ++i) dis[i] = inf;
dis[1] = 0;
db ans = 0;
for (int i = 1; i < n; ++i){ //选n-1条边
int u = 0;
for (int j = 1; j <= n; ++j)
if (!vis[j] && dis[j] < dis[u]) u = j;
vis[u] = 1; //因为之前我把ans写在这里，而i<n，所以最后一个点没有被统计到，就WA了
for (int v = 1; v <= n; ++v)
if (!vis[v]) dis[v] = min(dis[v], s[u][v].c - mid * s[u][v].w);
}
for (int i = 1; i <= n; ++i) ans += dis[i];
return ans <= 0;
}
inline void solve(){
for (int i = 1; i <= n; ++i)
scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
s[i][j] = s[j][i] = (Edge){(db)abs(p[i].z - p[j].z), dist(p[i], p[j])}; //计算出长度和高度
db l = 0, r = 1000;
while (l + eps < r){
db mid = (l + r) / 2;
if (check(mid)) r = mid; //要尽可能小
else l = mid;
}
printf("%.3lf\n", r);
}
int main(){
while (1){
scanf("%d", &n);
if (!n) break;
solve();
}
return 0;
}


/*这是一道好题，其中每个步骤各种变量都不一样（可能是我的问题），总之细节多

*/
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
struct Edge{ int u, v, e;}s[N];
struct S_Edge{ int v, e;}p[N];
struct Map_Edge{ int v, e, nxt;}E[N << 1];
int n, m, cnt, ans, block, tot, totS, tote, S;
int fa[N], hd[N], h[N], used[N], dis_max[N];
map<string, int> mp;
priority_queue<int> pq;
inline bool comp(Edge a, Edge b){ return a.e < b.e;} //用于排序与1节点不相连的边
inline bool cmp(S_Edge a, S_Edge b){ return a.e < b.e;} //用于排序与1相连的边
inline void add(int u, int v, int e){ E[++tote] = (Map_Edge){v, e, hd[u]}, hd[u] = tote;} //用于dfs
int Find(int x){
if (x == fa[x]) return x;
return fa[x] = Find(fa[x]);
}
int dfs(int u, int fat){ //算出1到每个节点路径上的最大值
for (int i = hd[u]; i; i = E[i].nxt){
int v = E[i].v;
if (v == fat) continue;
dis_max[v] = max(dis_max[u], E[i].e);
dfs(v, u);
}
}
int main(){
cin >> n;
for (int i = 1; i <= n; ++i){
string name1, name2; int val;
cin >> name1 >> name2 >> val;
if (name2 == "Park") swap(name1, name2);
if (!mp[name1]) mp[name1] = ++cnt; //用map来为每个人分配编号
if (!mp[name2]) mp[name2] = ++cnt;

if (name1 == "Park") p[++totS] = (S_Edge){mp[name2], val}; //分类加边
else s[++tot] = (Edge){mp[name1], mp[name2], val};
}
cin >> m; S = mp["Park"];

sort(s + 1, s + tot + 1, comp);
for (int i = 1; i <= cnt; ++i) fa[i] = i; //请注意点集大小是cnt，之前WA在这里
for (int i = 1; i <= tot; ++i){
int u = Find(s[i].u), v = Find(s[i].v);
if (u == v) continue;
ans += s[i].e;
fa[v] = u;
}

for (int i = 1; i <= cnt; ++i) //算连通块个数，如果一个点自己就是并查集的根就说明有一个连通块
block += (Find(i) == i) * (i != S);

sort(p + 1, p + totS + 1, cmp);
for (int i = 1; i <= totS; ++i){ //1向各个连通块连边
if (h[Find(p[i].v)]) continue; //说明该个点所在的连通块已经连入
h[Find(p[i].v)] = 1; used[i] = 1; //used是为了之后换边时跳过已经使用的边
ans += p[i].e;
}

dfs(S, 0); //计算dis_max
for (int i = 1; i <= totS; ++i){
if (used[i]) continue;
pq.push(dis_max[p[i].v] - p[i].e); //把换边后能降低的代价放入大根堆中，肯定减得多的更优
}
//注意这里的三个结束条件：没有换边的机会了、可用的边没了、当前换边不会更优了。之前这里没写全，WA了
for (int i = 1; i <= m - block && pq.size() && pq.top() > 0; ++i)
ans -= pq.top(), pq.pop();

cout << "Total miles driven: " << ans << endl;
return 0;
}



/*Kruskal练手题

(u,v,e)之后，那么e'>e，则那条边连接的两个集合的连边一定大于e+1，这

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6005;
struct Edge{
int u, v, e;
}s[N];
int T, n, fa[N], sz[N];
ll ans;
inline void clear(){
ans = 0;
for (int i = 1; i <= n; ++i)
fa[i] = i, sz[i] = 1;
}
inline bool comp(Edge a, Edge b){
return a.e < b.e;
}
int Find(int x){
if (fa[x] == x) return x;
return fa[x] = Find(fa[x]);
}
inline void Merge(int x, int y){
fa[y] = x, sz[x] += sz[y];
}
int main(){
scanf("%d", &T);
while (T --){
scanf("%d", &n);
clear(); //清空
for (int i = 1; i < n; ++i)
scanf("%d%d%d", &s[i].u, &s[i].v, &s[i].e);
sort(s + 1, s + n, comp);
for (int i = 1; i < n; ++i){ //Kruskal
int u = Find(s[i].u), v = Find(s[i].v);
if (u == v) continue;
ans += (ll)(s[i].e + 1) * (sz[u] * sz[v] - 1); //算贡献，别忘开long long
Merge(u, v);
}
printf("%lld\n", ans);
}
return 0;
}



/*算是一个矩阵乘法优化DP吧

B[i,j]=min[1<=k<=p]{A[i,k]+A[k,j]}那么我们假设矩阵A的m次方，
A^m[i,j]，表示i到j经过m条边的最短路，进一步，我们可以推出式子
A^(r+m)[i,j]=min[1<=k<=p]{A^r[i,k]+A^m[k,j]}对比矩阵乘法，其

*/
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int n, m, S, T, tot, a[N];
struct Edge{
int u, v, e;
}s[N];
struct Matrix{ //以下为矩阵的一些基本操作
int mt[N][N];
Matrix(){
memset(mt, 0x3f, sizeof mt);
}
Matrix operator *(const Matrix t){
Matrix ans;
for (int i = 1; i <= tot; ++i)
for (int j = 1; j <= tot; ++j)
for (int k = 1; k <= tot; ++k)
ans.mt[i][j] = min(ans.mt[i][j], mt[i][k] + t.mt[k][j]);
return ans;
}
}mat;
inline Matrix unit(){
Matrix tmp;
for (int i = 1; i <= tot; ++i) //同一个点之间的距离是0
tmp.mt[i][i] = 0;
return tmp;
}
inline Matrix qpow(Matrix a, int b){ //快速幂
Matrix tmp = unit();
for (; b; b >>= 1, a = a * a)
if (b & 1) tmp = tmp * a;
return tmp;
}
int main(){
scanf("%d%d%d%d", &n, &m, &S, &T);
for (int i = 1; i <= m; ++i){
scanf("%d%d%d", &s[i].e, &s[i].u, &s[i].v);
a[i * 2 - 1] = s[i].u;
a[i * 2] = s[i].v;
}
sort(a + 1, a + m * 2 + 1);
tot = unique(a + 1, a + m * 2 + 1) - a - 1; //离散化
for (int i = 1; i <= m; ++i){
s[i].u = lower_bound(a + 1, a + tot + 1, s[i].u) - a;
s[i].v = lower_bound(a + 1, a + tot + 1, s[i].v) - a;
int u = s[i].u, v = s[i].v;
mat.mt[u][v] = mat.mt[v][u] = min(mat.mt[u][v], s[i].e); //建图
}
S = lower_bound(a + 1, a + tot + 1, S) - a;
T = lower_bound(a + 1, a + tot + 1, T) - a;
mat = qpow(mat, n); //快速幂
printf("%d\n", mat.mt[S][T]);
return 0;
}



/*波折的题目，发现最后是没开long long

j的最短路长度。于是min[1<=i<j<k]{d[i][j]+f[j][k]+f[k][j]}就表示，由编号不

*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105, inf = 0x3f3f3f3f;
int n, m, ans = inf, f[N][N], d[N][N], pos[N][N];
vector<int> path;
void get_path(int u, int v){ //找u到v的最短路中经过的点
if (!pos[u][v]) return;
get_path(u, pos[u][v]);
path.push_back(pos[u][v]);
get_path(pos[u][v], v);
}
int main(){
scanf("%d%d", &n, &m);
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; ++i) f[i][i] = 0;
for (int i = 1; i <= m; ++i){
int u, v, e;
scanf("%d%d%d", &u, &v, &e);
f[u][v] = f[v][u] = min(f[u][v], e);
}

memcpy(d, f, sizeof f); //我们需要原图和最短路图
for (int k = 1; k <= n; ++k){
for (int i = 1; i < k; ++i) //注意不超过k
for (int j = i + 1; j < k; ++j)
if ((ll)d[i][j] + f[j][k] + f[k][i] < ans){
ans = d[i][j] + f[j][k] + f[k][i];
path.clear();
path.push_back(i); get_path(i, j); //存路径
path.push_back(j); path.push_back(k);
}
for (int i = 1; i <= n; ++i) //继续Floyd，更新d
for (int j = 1; j <= n; ++j)
if (d[i][k] + d[k][j] < d[i][j]){
d[i][j] = d[i][k] + d[k][j]; pos[i][j] = k;
}
}

if (ans == inf){
puts("No solution."); return 0;
}
for (int i = 0; i < path.size(); ++i)
printf("%d ", path[i]);
puts("");
return 0;
}



/*Floyd传递闭包

*/
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n, m, F[N][N], G[N][N], In_Degree[N];
queue<int> q;
inline void Clear(){
memset(F, 0, sizeof F);
memset(G, 0, sizeof G);
memset(In_Degree, 0, sizeof In_Degree);
}
inline void Floyd(){
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
F[i][j] |= F[i][k] & F[k][j];
}
inline void Work(int T){ //拓扑排序
for (int i = 0; i < n; ++i)
if (!In_Degree[i]) q.push(i);
printf("Sorted sequence determined after %d relations: ", T);
while (q.size()){
int u = q.front(); q.pop();
putchar(u + 'A');
for (int v = 0; v < n; ++v)
if (G[u][v]){
--In_Degree[v];
if (!In_Degree[v]) q.push(v);
}
}
puts(".");
}
inline void Solve(){
int Fail = 0, Not_Find = 0, T;
for (int i = 1; i <= m; ++i){
char st[10];
scanf(" %s", st);
if (Not_Find || Fail) continue; //满足两种特殊情况之一
char u = st[0] - 'A', v = st[2] - 'A';

F[u][v] = G[u][v] = 1; //关系图和原图
++In_Degree[v]; //入度，之后做拓扑排序
Floyd();

Not_Find = 1;
for (int u = 0; u < n; ++u){
if (F[u][u]){Fail = 1; break;} //出现矛盾
for (int v = 0; v < n; ++v)
if (u != v && !F[u][v] && !F[v][u]) Not_Find = 0; //没有找到大小关系，任不能判断
}

T = i;
}
if (Fail) printf("Inconsistency found after %d relations.\n", T);
else if (!Not_Find) printf("Sorted sequence cannot be determined.\n");
else Work(T);
}
int main(){
while (1){
Clear();
scanf("%d%d", &n, &m);
if (n + m == 0) break;
Solve();
}
return 0;
}



/*像这种看似很简单实则复杂的题是很有思维含量的

2.加入单向边，统计连通块的入度deg[i]。
3.用一个队列做拓扑序，将入度为0的连通块入队。
4.取出队首连通块，做Dijsktra
Dijsktra的具体步骤：
(1)将所有点入堆（因为我们并不知道具体有哪些点被更新了，全部入堆比较方便）
(2)取出x，扩展过就跳过，不然扫描所有出边，用dis[x]+e更新dis[y]
(3)若c[x]==c[y]，且y被更新了，就入堆
(4)若c[x]!=c[y]，那么deg[c[y]]减一。若成了0，则将c[y]入队，加入拓扑序中
(5)重复以上步骤，直到堆空
5.重复以上步骤，直到队列为空

d都不会经过，但做完a后，d中的点全是inf，但有可能通过负权单向边使得结果比b中的inf点小。
*/
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 25005, M = 50005, inf = 0x3f3f3f3f;
struct Edge{
int v, e, nxt;
}E[M * 3];
int T, R, P, S, cnt, tot, hd[N];
int c[N], dis[N], deg[N], vis[N];
vector<int> point[N];
priority_queue<pii, vector<pii>, greater<pii> > p;
queue<int> q;
inline void add(int u, int v, int e){
E[++tot] = (Edge){v, e, hd[u]}, hd[u] = tot;
}
void dfs(int u){
c[u] = cnt; point[cnt].push_back(u);
for (int i = hd[u]; i; i = E[i].nxt)
if (!c[E[i].v]) dfs(E[i].v);
}
inline void Dijkstra(int id){
for (int i = 0; i < point[id].size(); ++i) //无脑入队
p.push({dis[point[id][i]], point[id][i]});
while (p.size()){ //Dijsktra板子
int u = p.top().second; p.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = hd[u]; i; i = E[i].nxt){
int v = E[i].v;
if (c[u] == c[v]){ //分类讨论
if (dis[u] + E[i].e < dis[v])
dis[v] = dis[u] + E[i].e, p.push({dis[v], v});
}else{
if (dis[u] + E[i].e < dis[v]) dis[v] = dis[u] + E[i].e;
--deg[c[v]];
if (!deg[c[v]]) q.push(c[v]);
}
}
}
}
int main(){
scanf("%d%d%d%d", &T, &R, &P, &S);
for (int i = 1; i <= R; ++i){
int u, v, e;
scanf("%d%d%d", &u, &v, &e);
}

/*解释一下这里为什么不用保证S所在连通块必须先入队
以为第一批入队的连通块没有入度，也就是说S不可能更新到这些点，所以就不用特判了
*/
for (int i = 1; i <= T; ++i) //划分连通块
if (!c[i]) ++cnt, dfs(i);

for (int i = 1; i <= P; ++i){
int u, v, e;
scanf("%d%d%d", &u, &v, &e);
if (c[u] != c[v]) ++deg[c[v]]; //入度
}

for (int i = 1; i <= cnt; ++i)
if (!deg[i]) q.push(i);
memset(dis, 0x3f, sizeof dis);
dis[S] = 0;
while (q.size()){ //拓扑排序
Dijkstra(q.front()); q.pop();
}

for (int i = 1; i <= T; ++i){
if (dis[i] >= inf / 2) puts("NO PATH");
else printf("%d\n", dis[i]);
}
return 0;
}



/*基础题

n路径上的最大值。可知这并不满足Dijsktra，所以要用spfa实现。答案可以即是所有点中
dis[1][x]-dis[0][x]的最大值。可以证明不会有遗漏情况。

*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 5e5 + 5, inf = 0x3f3f3f3f;
struct Edge{
int v, nxt;
}E[2][M * 2];
int n, m, ans;
int tot[2], hd[2][N], vis[N], dis[2][N], price[N];
queue<int> q;
inline void add0(int u, int v){ //存图
E[0][++tot[0]] = (Edge){v, hd[0][u]}, hd[0][u] = tot[0];
}
inline void add1(int u, int v){ //存反图
E[1][++tot[1]] = (Edge){v, hd[1][u]}, hd[1][u] = tot[1];
}
inline int check(int u, int v, int type){ //都是为了偷懒只写一个spfa
if (type == 0) return min(dis[type][u], price[v]) < dis[type][v];
else return max(dis[type][u], price[v]) > dis[type][v];
}
inline int calc(int u, int v, int type){
if (type == 0) return min(dis[type][u], price[v]);
else return max(dis[type][u], price[v]);
}
inline void spfa(int origin, int type, int origin_val){
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; ++i)
dis[type][i] = origin_val;
dis[type][origin] = price[origin];
q.push(origin);
while (q.size()){
int u = q.front(); q.pop();
vis[u] = 0;
for (int i = hd[type][u]; i; i = E[type][i].nxt){
int v = E[type][i].v;
if (check(u, v, type)){ //更新最大或最小值
dis[type][v] = calc(u, v, type);
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", price + i);
for (int i = 1; i <= m; ++i){
int u, v, type;
scanf("%d%d%d", &u, &v, &type);
if (type == 1) add0(u, v);