PAT复习自用——做题解和写过代码的搬运工
//图论
/*
前言：代码量较大，模板比较固定，实际问题考查较多
*/
//基本工具
//边集合，用于有些模拟问题按照边判断条件是否满足
struct Edge
{
int x,y;
}e[N];
int g[N][N];//邻接矩阵，注意题目要求是无向图还是有向图，如果是无向图则两点都要加边
vector<int> g[N];//邻接表，同一般树的存储
bool st[N];//使用条件：1）遍历的时候防止出现环的情况 2）Dijkstra
void dijkstra(int start);
//图的遍历---同树，只需要多标记好st数组即可
//另外，图的连通性可以使用并查集作为工具
void dfs();
void bfs();
-----------------------
/*
（一）单源最短路问题——Dijkstra
*/
/*
常考问题：多关键字的Dijkstra、Dijkstra求路径、Dijkstra多路径、堆优化版本Dijkstra
理解好Dijkstra每一次迭代都会唯一确定一个点的最短距离
第一次迭代时选中起点（初始化的时候起点设置d=0，第一次会被选中），更新d邻接的点
而后每一次迭代都选择d最小的点，选中则该点的d不会再改变——贪心策略
如果出现多条路径则表示该次迭代有几条距离相等的点
*/
------------------------------
//模板
//1、普通Dijkstra模板
const int N = 1010,INF = 0x3f;
int g[N][N],d[N];
bool st[N];
int n,m;
void dijkstra()
{
memset(d,INF,sizeof d);
memset(st,0,sizeof st);
d[1] = 0;
for(int i = 0;i<n;i++)
{
int t = -1;
for(int j = 1;j<=n;j++)
if(!st[j]&&(t==-1||d[j]<d[t]))t = j;
st[t] = true;
for(int j = 1;j<=n;j++)
d[j] = min(d[j],d[t]+g[t][j]);
}
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i = 0;i<m;i++)
{
int x,y,z;cin>>x>>y>>z;
g[x][y] = min(z,g[x][y]);
}
dijkstra();
if(d[n]==0x3f3f3f3f)cout<<-1<<endl;//memset中的0x3f = 实际输出的 0x3f3f3f3f
else cout<<d[n]<<endl;
return 0;
}
//2、堆优化版本Dijkstra
//当存储节点较多的时候需要使用邻接表存储图，这里使用unordered_map比较方便
const int N = 1000000 ;
typedef pair<int,int> PII;
int n,m,d[N];
unordered_map<int,unordered_map<int,int>> e;
bool st[N];
int dijkstra()
{
memset(d,0x3f,sizeof d);
memset(st,0,sizeof st);
priority_queue<PII, vector<PII>, greater<PII>> heap;
d[1] = 0,heap.push({0,1});
for(int i = 0;i<n;i++)
{
auto t = heap.top();
heap.pop();
int v = t.second,dist = t.first;
if(st[v])continue;//这条语句比较关键，需要控制之前已确定最短路的节点不再访问
st[v] = true;
for(auto c:e[v])
{
int j = c.first;
if(dist+e[v][j]<d[j])
d[j] = dist+e[v][j],
heap.push({d[j],j});
}
}
if(d[n]==0x3f3f3f3f||d[n]<0)return -1;
//小于0的情况对应可能溢出或者可能错误对不可达节点进行了赋值，错误当前没找到
else return d[n];
}
int main()
{
cin>>n>>m;
while(m--)
{
int a,b,c;cin>>a>>b>>c;
if(!e[a].count(b))e[a][b] = c;
e[a][b] = min(e[a][b],c);
}
cout<<dijkstra()<<endl;
return 0;
}
------------------------------
//题型一：第二关键字为点权
//PAT-1003 紧急情况
//解法一：Dijkstra
const int N = 1010;
int g[N][N],d[N],w[N],cnt[N],num[N],s,e,n,m;//邻接矩阵，距离，点权重，最短路径数量，第二关键字最优解
bool st[N];
void dijkstra()
{
memset(st,0,sizeof st);
memset(d,0x3f,sizeof d);
d[s] = 0,cnt[s] = 1,num[s] = w[s];
for(int i = 0;i<n;i++)
{
int t = -1;
for(int j = 0;j<n;j++)
if(!st[j]&&(t==-1||d[t]>d[j]))//遍历找寻最短的d
t = j;
st[t] = true;
for(int j = 0;j<n;j++)//g被初始化为0x3f才可以这么做，否则没有边的地方会按照0来走，导致都是0
if(d[t]+g[t][j]<d[j])
{
cnt[j] = cnt[t];
d[j] = d[t]+g[t][j];
num[j] = num[t]+w[j];
}
else if(d[t]+g[t][j]==d[j])//多关键字
{
cnt[j]+=cnt[t];
num[j] = max(num[j],num[t]+w[j]);
}
}
}
int main()
{
cin>>n>>m>>s>>e;
for(int i = 0;i<n;i++)cin>>w[i];
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;cin>>a>>b>>c;
g[a][b] = g[b][a] = min(c,g[a][b]);
}
dijkstra();
cout<<cnt[e]<<" "<<num[e]<<endl;
return 0;
}
//解法二：dfs
const int N = 100100;
typedef pair<int,int>PII;
int n,m,s,e,minL = 0x3f3f,cnt = 0,w[N],maxnum = 0;
bool st[N];
vector<PII> g[N];// edge weight,destination
vector<PII> path;//所有可达终点的路径 d,num
void dfs(int u,int num,int nowd)//当前结点，当前结点的救援队数量，当前距离
{
if(nowd>minL)return;//剪枝
if(u==e)
path.push_back({nowd,num}),minL = min(nowd,minL);
else
{
for(auto c:g[u])
{
int dest = c.first,weight = c.second;
if(!st[dest])
{
st[dest] = true;
dfs(dest,num+w[dest],nowd+weight);
st[dest] = false;
}
}
}
}
int main()
{
cin>>n>>m>>s>>e;
for(int i = 0;i<n;i++)cin>>w[i];
for(int i = 0;i<m;i++)
{
int a,b,c;cin>>a>>b>>c;
g[a].push_back({b,c}),g[b].push_back({a,c});
}
dfs(s,w[s],0);
for(auto c:path)
{
if(c.first==minL)
{
cnt++;
if(c.second>maxnum)maxnum = c.second;
}
}
cout<<cnt<<" "<<maxnum<<endl;
return 0;
}
-------------------------------------------
//题型二：第二关键字为边权，要求记录路径，尤其注意不要忘记边权要初始化为0x3f
//路径使用pre数组记录，在Dijkstra的过程中被赋值为前驱结点，最后输出从终点往前递归搜
//PAT-1030 旅行计划
void dfs(int u)//递归输出pre
{
if(u==s)//递归的返回条件是到达起点，而不是没有前驱的点
{
cout<<s<<" ";
return;
}
dfs(pre[u]);
cout<<u<<" ";
}
//下面看一下pre怎么更新
void dijkstra()
{
memset(st,0,sizeof st);
memset(d,0x3f,sizeof d);
memset(c,0x3f,sizeof c);
d[s] = 0,c[s] = 0;
for(int i = 0;i<n;i++)
{
int t = -1;
for(int j = 0;j<n;j++)
if(!st[j]&&(t==-1||d[t]>d[j]))
t = j;
st[t] = true;
for(int j = 0;j<n;j++)
if(d[t]+g[t][j]<d[j])
{
d[j] = d[t]+g[t][j];
pre[j] = t;
c[j] = c[t]+cost[t][j];
}
else if(d[t]+g[t][j]==d[j]&&c[j]>c[t]+cost[t][j])
{
c[j] = cost[t][j]+c[t];
pre[j] = t;
}
}
}
int main()
{
cin>>n>>m>>s>>e;
memset(g,0x3f,sizeof g);
memset(cost,0x3f,sizeof cost);
memset(pre,-1,sizeof pre);
while(m--)
{
int a,b,c,d;cin>>a>>b>>c>>d;
g[a][b] = g[b][a] = min(c,g[a][b]);
cost[a][b] = cost[b][a] = min(d,cost[a][b]);
}
dijkstra();
dfs(e);
cout<<d[e]<<" "<<c[e];
return 0;
}
--------------------
//题型三：三个关键字：同时考虑点权和边的数量
//PAT-1087 条条大路通罗马
if(d[v]>d[u]+G[u][v])//短
{
d[v] = d[u]+G[u][v];
count[v] = count[u]+1;
happy[v] = happy[u]+h[v];
pre[v] = u;
num[v] = num[u];
}
else if(d[v]==d[u]+G[u][v])//更新边的数量（第三关键字），幸福指数（第二关键字），
{
if(happy[v]==happy[u]+h[v])//一样辛福
{
if(count[u]<count[v])//找到平均更辛福的了
{
count[v] = count[u];
pre[v] = u;
}
}
else if(happy[v]<happy[u]+h[v])//找到更辛福的了
{
happy[v] = happy[u]+h[v];
pre[v] = u;
count[v] = count[u]+1;
}
num[v] = num[u]+num[v];//更新第一关键字路径数目
}
---------------------------------------------
//PAT-1131 地铁地图
/*
本题看似是一个搜索问题，但其实只要换一种建图方式，将一个链路钟的每个点都变成互联的网络
而不是只保留前驱和后继，改变这个建图方式以后就将问题转变为双关键字的dijkstra问题，第一关键字为线路长度，第二关键字为换乘线路次数
本题的难度在于时间卡的比较紧张，因此需要使用堆优化的dijkstra
本题比较麻烦的地方在于如何保存线路信息，使用格式化的字符串，存储在map中是我想到的方法，
自定义格式为：format(u)+format(v)+to_string(dist)
*/
using namespace std;
typedef pair<int,int> PII;
const int N = 10010,M = 1e6+10;
vector<PII> g[N];
unordered_map<string,int>line;
int n,d[N],stops[N],cnt[N],pre[N];
bool st[N];
string info[N];
string format(int n)//补充0
{
string res = to_string(n);
while(res.size()<4)res ="0" + res;
return res;
}
void dijkstra(int start,int end)
{
memset(d,0x3f,sizeof d);
memset(st,0,sizeof st);
d[start] = 0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,start});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int u = t.second;
if(u==end)break;
if(st[u])continue;
st[u] = true;
for(auto c:g[u])
{
int v = c.first,dist = c.second;
if(d[v]>d[u]+dist)
{
pre[v] = u;
cnt[v] = cnt[u];
d[v] = dist+d[u];
heap.push({d[v],v});
string ask = format(u)+format(v)+to_string(dist);
info[v] = "Take Line#"+to_string(line[ask])
+" from "+format(u)+" to "+format(v)+".";
}
else if(d[v]==d[u]+dist&&cnt[v]>cnt[u]+1)
{
pre[v] = u;
cnt[v] = cnt[u]+1;
string ask = format(u)+format(v)+to_string(dist);
info[v] = "Take Line#"+to_string(line[ask])
+" from "+format(u)+" to "+format(v)+".";
//此时不用加到堆中
}
}
}
vector<string>res;
cout<<d[end]<<endl;
for(int i = end;i!=start;i = pre[i])res.push_back(info[i]);
for(int i = res.size()-1;i>=0;i--)
cout<<res[i]<<endl;
}
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{
int cnt,len;cin>>cnt;
for(int j = 0;j<cnt;j++)cin>>stops[j];
for(int j = 0;j<cnt;j++)
for(int k = 0;k<j;k++)
{
if(stops[0]!=stops[cnt-1])len = j-k;
else len = min(j-k,cnt-1-j+k);
string sj = format(stops[j])+format(stops[k])+to_string(len);
string sk = format(stops[k])+format(stops[j])+to_string(len);
line[sj] = i,line[sk] = i;
g[stops[j]].push_back({stops[k],len});
g[stops[k]].push_back({stops[j],len});
}
}
int k;cin>>k;
while(k--)
{
int start,end;
cin>>start>>end;
dijkstra(start,end);
}
return 0;
}
//拯救007---二维平面dijkstra，要手动建边，同时因为这种建边方式比较稠密，需要用优先队列维护可达
//注意这里逃脱的条件是到达正方形的边，而不是到达正方形的四个顶点的距离
//本题只需要搜索所有解中是否有合理的解，故直接bfs
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int N = 1010;
int n, d;
bool st[N];
struct Cro
{
int x, y;
}c[N];
int calc(int x1, int y1, int x2, int y2)
{
int dx = x1 - x2;
int dy = y1 - y2;
dx *= dx, dy *= dy;
return dx + dy;
}
int dist[N][N],escape[N];
int main()
{
cin >> n >> d;
priority_queue<int,vector<int>,greater<int>>q;
memset(dist, 0x3f3f3f3f, sizeof dist);
int can = d * d;
for (int i = 0; i < n; i++)
{
cin >> c[i].x >> c[i].y;
if (calc(0, 0, c[i].x, c[i].y) <= (15 + d) * (15 + d))q.push(i);
}
for (int i = 0; i < n; i++)
{
int x = c[i].x, y = c[i].y;
escape[i] = min(min(min(abs(50 - x), abs(50 - y)), abs(-50 - x)), abs(-50 - y));
escape[i] *= escape[i];
for (int j = 0; j < n; j++)
dist[i][j] = calc(c[i].x, c[i].y, c[j].x, c[j].y);
}
bool flag = false;
while (!q.empty())
{
int t = q.top();
q.pop();
if (st[t])continue;
if (escape[t] <= can)
{
flag = true;
break;
}
st[t] = true;
for(int i = 0;i<n;i++)
if (!st[i]&&dist[t][i] <= can)
q.push(i);
}
if (flag)puts("Yes");
else puts("No");
return 0;
}
//hard-version 需要使得距离最短，故需要进行两步预处理，第一个和上面一样，需要将第一脚的队列储存
//第二个处理，终点可以预处理出来也是一个队列，故只要从每个第一步出发，求一次dijkstra，限定终点时候选节点
//每次dijkstra得到一个解，从这些解中选择最优的，并存储这条路径，注意这里的最优指的是经过的边数最少
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 1001;
int n, d, minstep = 0x3f3f3f3f,temp[N],res[N],dist[N][N],S,E,s,step[N];
struct Cro
{
int x, y;
}c[N];
priority_queue<PII, vector<PII>, greater<PII>> heap;//first step--- dfs start
set<int> last;//last step--- dfs exit
bool st[N];
double calc(int x1, int y1, int x2, int y2)
{
int dx = (x1 - x2) * (x1 - x2);
int dy = (y1 - y2) * (y1 - y2);
return (double)sqrt((dx + dy));
}
void dfs(int u,int step)
{
st[u] = true;
if (last.count(u))
{
if (step < minstep)
{
minstep = step;
for (int i = 0; i < n; i++)
res[i] = temp[i];
S = s;
E = u;
return;
}
}
for(int i = 0;i<n;i++)
if (!st[i] && dist[u][i] != 0x3f3f3f3f)
{
temp[i] = u;
dfs(i,step+1);
}
}
void bfs(int u)
{
memset(st, 0, sizeof st);
memset(step, 0x3f, sizeof step);
queue<int>q;
q.push(u);
step[u] = 1;
while (!q.empty())
{
int t = q.front();
q.pop();
st[t] = true;
if (last.count(t)&&step[t]<minstep)
{
for (int i = 0; i < n; i++)
res[i] = temp[i];
minstep = step[t];
S = u;
E = t;
}
for (int i = 0; i < n; i++)
{
if (!st[i]&&dist[t][i]!=0x3f3f3f3f)
{
q.push(i);
temp[i] = t;
step[i] = step[t] + 1;
}
}
}
}
int main()
{
cin >> n >> d;
if (d >= 50 - 7.5)
{
minstep = 1;
cout << 1 << endl;
return 0;
}
memset(dist, 0x3f, sizeof dist);
for (int i = 0; i < n; i++)
{
int x, y; cin >> x >> y;
c[i] = { x,y };
double d0 = calc(0, 0, x, y);
if (d0 >= 7.5) d0 = d0 - 7.5;
else d0 = 0;
if (d0 <= d)heap.push({ d0,i });
if (abs(x - 50) <= d || abs(x + 50) <= d
|| abs(y - 50) <= d || abs(y + 50) <= d)
last.insert(i);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int x1 = c[i].x, x2 = c[j].x, y1 = c[i].y, y2 = c[j].y;
double dij = calc(x1, y1, x2, y2);
if (dij <= d)dist[i][j] = dist[j][i] = dij;
}
while (heap.size())
{
memset(st, 0, sizeof st);
auto t = heap.top();
heap.pop();
s = t.second;
//dfs(s, 1);dfs有一个测试样例没过，使用bfs正确
bfs(s);
}
if (minstep != 0x3f3f3f3f)
{
cout << minstep + 1 << endl;
vector<int> path;
for (int i = E; i != S; i = res[i])
path.push_back(i);
path.push_back(S);
reverse(path.begin(), path.end());
for (auto t : path)
cout << c[t].x << " " << c[t].y << endl;
}
else cout << 0 << endl;
return 0;
}
---------------------------------------------
/*
Bellman-Ford && SPFA 解决dijkstra的不能有负权问题
*/
---------------------------------------------
/*
（二）图的遍历以及图的搜索
*/
/*
图的连通特性可以使用并查集维护，也可以使用dfs进行连通性判断
图的遍历方式有dfs，bfs，枚举，并查集
*/
int dfs(int u)//dfs求连通块的大小
{
st[u] = true;
int res = 1;
for(int i = 1;i<=n;i++)
if(!st[i]&&g[u][i])
res+=dfs(i);
return res;
}
//判断连通性的最简便写法是使用并查集
int find(int x)
{
return x==p[x]?x:p[x] = find(p[x]);
}
//这种更新方式在最小生成树的kruskal算法中还有体现
bool check()
{
int cnt = n;
for(auto c:edge)
{
int pa = find(c.first),pb = find(c.second);
if(pa!=pb)cnt--,p[pa] = pb;
}
return cnt==1;//连通块的大小是n-cnt+1
}
---------------------------------------------
//图两点之间搜索所有路径
void dfs(int u)
{
st[u] = true;
path.push_back(u);
if(u==e)
{
for(auto c:path)cout<<c<<" ";
cout<<endl;
}
for(auto c:g[u])if(!st[c])dfs(c);
st[u] = false;
path.pop_back();
}
---------------------------------------------
/*
六度空间——图论搜索练习题：最后一个测试样例没过
“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：
“你和任何一个陌生人之间所间隔的人不会超过六个，
也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，
试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，
这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，
能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
*/
//每个点深搜一次，只搜索6层
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 1001;
vector<int>g[N];
int n,m;
bool st[N];
int dfs(int u,int d)
{
int cnt = 1;
st[u] = true;
if(d>=6)return cnt;
for(auto c:g[u])
if(!st[c])cnt+=dfs(c,d+1);
return cnt;
}
int main()
{
cin>>n>>m;
for(int i = 0;i<m;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1;i<=n;i++)
{
memset(st,0,sizeof st);
int cnt = dfs(i,0);
printf("%i: %.2lf%\n",i,double(cnt)*100/n);
}
return 0;
}
---------------------------------------------
//PAT-1034 最大团伙---不错的练习题
//解法一：使用并查集维护连通团伙，使用并查集和dfs的区别在于输入的时候就进行集合合并，是一个动态过程
//而dfs是事先存好所有节点，然后静态访问，因此动态的缺点就在于无法获得头目，需要再静态做一次遍历
const int N = 1001;
int n,k,idx = 0;
unordered_map<string,int> s2i,num;
unordered_map<int,int> head;//将之前的head映射到gang数组的id
unordered_map<int,string> i2s;
int p[N*2],g[N*2][N*2],s[N*2];
vector<pair<string,int>>gang;
vector<int>G[N];
int find(int x)
{
return x==p[x]?x:p[x] = find(p[x]);
}
int main()
{
cin>>n>>k;
memset(s,0,sizeof s);memset(g,0,sizeof g);
for(int i = 0;i<N*2;i++)p[i] = i;
for(int i = 0;i<n;i++)
{
string a,b;int t;
cin>>a>>b>>t;
if(!s2i.count(a))s2i[a] = idx,i2s[idx++] = a;
if(!s2i.count(b))s2i[b] = idx,i2s[idx++] = b;
int ia = s2i[a],ib = s2i[b];
g[ia][ib]+=t,g[ib][ia]+=t;
s[ia]+=t,s[ib]+=t;
p[find(ia)] = find(ib);
//这里无法直接按秩合并，因为目前的祖先可能未来会被超越，
//出现原因是一个元素可能在合并过程中修改秩多次
}
int nidx = 0;//gang数组的下标
for(int i = 0;i<idx;i++)
{
int h = find(i);
if(!head.count(h))head[h] = nidx++;
G[head[h]].push_back(i);
}
for(int i = 0;i<nidx;i++)//统计每个gang中的总权重，遍历得到头目（因为并查集合并的时候没能解决掉这个问题）
{
auto c = G[i];
int maxid = 0,maxtime = 0,total = 0,cnt = 0;
for(auto d:G[i])
{
if(s[d]>maxtime)maxtime = s[d],maxid = d;
total+=s[d],cnt++;
}
string id = i2s[maxid];
if(c.size()>=3&&total/2>k)gang.push_back({id,total}),num[id] = cnt;
}
sort(gang.begin(),gang.end());
cout<<gang.size()<<endl;
for(auto c:gang)cout<<c.first<<" "<<num[c.first]<<endl;
return 0;
}
//解法二：dfs
unordered_map<string,vector<pair<string,int>>> g;
unordered_map<string,bool>st;
unordered_map<string,int>total;
typedef pair<string,int> Gang;
int n,k;
int dfs(string u,vector<string>& member)//注意使用vector引用，便于退出时遍历得到头目
{
st[u] = true;
string head = u;
member.push_back(u);
int sum = 0;
for(auto c:g[u])
{
string v = c.first;
sum+=c.second;
if(!st[v])sum+=dfs(v,member);//如果没有访问过，则加入该节点，并得到该节点所有权重
}
return sum;
}
vector<Gang> res;
int main()
{
cin>>n>>k;
for(int i = 0;i<n;i++)
{
string a,b;int t;
cin>>a>>b>>t;
g[a].push_back({b,t}),g[b].push_back({a,t});
total[a]+=t,total[b]+=t;
}
for(auto c:total)
{
string id = c.first;
if(!st[id])
{
vector<string> members;
int sum = dfs(id,members);
sum/=2;//无向图边访问两次，因此要除掉
if(sum>k&&members.size()>=3)
{
string head = members[0];
for(auto member:members)
if(total[member]>total[head])
head = member;
res.push_back({sum,head,members});
}
}
}
cout<<res.size()<<endl;
sort(res.begin(),res.end());
for(auto c:res)cout<<c.head<<" "<<c.member.size()<<endl;
return 0;
}
-----------------------------------------------------
/*
判断合法的dfs序列---模拟dfs，即受限dfs，根据访问序列进行dfs
*/
#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1001;
int n,m,g[N][N],seq[N],degree[N],tmp[N];
bool st[N];
vector<int>p[N];
bool check()
{
bool flag = true;
vector<int>s;s.push_back(seq[0]);//初始化栈
for(auto c:p[seq[0]])tmp[c]--;
for(int i = 1;i<n;i++)//使用vector模拟栈
{
if(s.size()==0){flag = false;break;}//没有可达的点
int v = seq[i],u = s.back();
if(g[u][v])
{
for(auto c:p[v])
{
tmp[c]--;
if(tmp[c]==0)
{
auto it = find(s.begin(),s.end(),c);//所有入边对应的顶点出度减一
if(it!=s.end())s.erase(it);
}
}
if(tmp[v])s.push_back(v);
if(tmp[v]==0&&i==n-2)break;//到达最后一个节点
}
else flag = false;//当前顶点和栈顶不相连
}
return flag;
}
int main()
{
cin>>n>>m;
while(m--)
{
int x,y;cin>>x>>y;
g[x][y] = 1;
p[y].push_back(x);
degree[x]++;
}
int cnt;
cin>>cnt;
while(cnt--)
{
for(int i = 0;i<n;i++){cin>>seq[i];tmp[i] = degree[i];}
if(check())puts("Yes");
else puts("No");
}
return 0;
}
/*那么问题来了，我们如何得到所有合法的dfs序列个数呢？
仔细思考这个问题，是一个复杂的栈序列个数问题，每次出栈的操作来源于后继节点的信号
我们先看看如何输出所有的合法dfs序列看看
*/
-----------------------------------------------------
/*
判断合法的bfs序列----解法十分巧妙，
https://www.cnblogs.com/00isok/p/9582197.html
就是模拟BFS，某个父亲节点的所有子节点必然是连续一段出现的(如果该BFS序合法的话)，所以每次从队列中弹出节点的时候，
就将对应位置连续的所有儿子全部标记，如果有儿子不是连续的出现在对应位置，则之后永远不会被标记到。
自然巧妙地将所有错误情况考虑进来了
*/
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int N = 100;
int n,m,seq[N];
bool st[N];
map<int,int> g[N];
void bfs()
{
queue<int>q;
q.push(seq[0]);int loc=1;
while(!q.empty()){
int u=q.front();
q.pop();
st[u]=1;
while(g[u][seq[loc]]){
//就是模拟BFS，
//将它接下来的儿子全部塞入队列，
//如果u的儿子不是连续的出现在这些位置，
//则永远不可能被标记到
q.push(seq[loc]);
loc++;
}
}
}
int main()
{
cin>>n>>m;
for(int i = 0;i<m;i++)
{
int x,y;cin>>x>>y;
g[x][y] = 1;
}
int k;cin>>k;
while(k--)
{
memset(st,0,sizeof st);
for(int i = 0;i<n;i++)
cin>>seq[i];
bfs();
bool flag = true;
for(int i = 0;i<n;i++)
if(st[seq[i]]!=1)flag = false;
if(flag)puts("Yes");
else puts("No");
}
return 0;
}
-----------------------------------------------------
/*
枚举问题：PAT-1142 最大团
*/
#include<iostream>
#include<cstring>
using namespace std;
const int N = 210,M = N*N;
struct edge
{
int x,y;
}e[N];
bool st[N];
int seq[N],n,m,g[N][N];
int main()
{
cin>>n>>m;
while(m--)
{
int x,y;cin>>x>>y;
g[x][y] = g[y][x] = 1;
}
int k;cin>>k;
while(k--)
{
memset(st,0,sizeof st);
int cnt;
cin>>cnt;
for(int i = 0;i<cnt;i++)
{
cin>>seq[i];
st[seq[i]] = true;
}
bool is_clique = true;
for(int i = 0;i<cnt-1;i++)
for(int j = i+1;j<cnt;j++)
if(!g[seq[i]][seq[j]])
{
is_clique = false;
break;
}
if(!is_clique)puts("Not a Clique");
else
{
bool is_max = true;
for(int i = 1;i<=n;i++)
{
bool ready = true;
if(st[i])continue;
for(int j = 0;j<cnt;j++)
if(!g[i][seq[j]])ready = false;
if(ready)is_max = false;
}
if(is_max)puts("Yes");
else puts("Not Maximal");
}
}
return 0;
}
-----------------------------------------------------
//PAT-1072 加油站 枚举，图论，最短路 坑点---浮点数精度+1e-8
#include<iostream>
#include<unordered_map>
#include<vector>
#include<set>
#include<algorithm>
#include<cstring>
#include<iomanip>
using namespace std;
const int N = 2000;
set<string>gas;
unordered_map<string,int>s2i;
unordered_map<int,string>i2s;
int d[N],g[N][N],n,m,k,ds,idx = 0;
double Average,Mindist;
bool st[N];
struct r
{
string id;
double mindist,average_dist;
bool operator <(r x)
{
if(x.mindist==mindist)
{
if(x.average_dist==average_dist)return id<x.id;
return average_dist<x.average_dist;
}
return mindist>x.mindist;
}
};
vector<r>res;
void dijkstra(int start)
{
memset(st,0,sizeof st);
memset(d,0x3f,sizeof d);
Mindist = 0x3f3f3f3f,Average = 0;
d[start] = 0;
for(int i = 0;i<n+m;i++)
{
int t = -1;
for(int j = 0;j<n+m;j++)
if(!st[j]&&(t==-1||d[t]>d[j]))t = j;
st[t] = true;
for(int j = 0;j<n+m;j++)
d[j] = min(d[j],d[t]+g[t][j]);
}
int cnt = 0;double average = 0;
for(int i = 0;i<n+m;i++)
{
if(gas.count(i2s[i]))continue;
if(d[i]>ds)return;
Mindist = min(int(Mindist),d[i]);
cnt++,Average+=d[i];
}
res.push_back({i2s[start],Mindist,Average/cnt+1e-8});
}
int main()
{
cin>>n>>m>>k>>ds;
memset(g,0x3f,sizeof g);
while(k--)
{
string a,b;int dist;cin>>a>>b>>dist;
if(!s2i.count(a))s2i[a] = idx,i2s[idx++] = a;
if(!s2i.count(b))s2i[b] = idx,i2s[idx++] = b;
if(a[0]=='G')gas.insert(a);
if(b[0]=='G')gas.insert(b);
g[s2i[a]][s2i[b]] = g[s2i[b]][s2i[a]] = dist;
}
for(auto c:gas)
{
int id = s2i[c];
dijkstra(id);
}
sort(res.begin(),res.end());
if(res.size())
{
cout<<res[0].id<<endl;
printf("%.1lf %.1lf\n",res[0].mindist,res[0].average_dist);
}
else puts("No Solution");
return 0;
}
-----------------------------------------------------
/*
同类题型：7-4 Ambulance Dispatch (30分)
链接：https://pintia.cn/problem-sets/1106490269907619840/problems/1106490594978766851
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2000;
bool st[N];
int w[N],d[N],g[N][N],n,m,k,cnt,pre[N],num[N];
int get_(string x)
{
if(x[0]=='A')return (x[2]-'0')+n;
else return stoi(x);
}
void dijkstra(int u)
{
memset(st,0,sizeof st);
memset(d,0x3f,sizeof d);
d[u] = 0;
for(int i = 0;i<n+m;i++)
{
int t = -1;
for(int j = 1;j<=n+m;j++)
if(!st[j]&&(t==-1||d[j]<d[t]))t = j;
st[t] = true;
for(int j = 1;j<=n+m;j++)
{
if(d[j]>d[t]+g[t][j])
{
pre[j] = t;
d[j] = d[t]+g[t][j];
num[j] = num[t]+1;
}
else if(d[j]==d[t]+g[t][j]&&num[j]>num[t]+1)
pre[j] = t,num[j] = num[t]+1;
}
}
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i = n+1;i<=n+m;i++)cin>>w[i];
cin>>k;
while(k--)
{
string x,y;int dist;cin>>x>>y>>dist;
int a = get_(x),b = get_(y);
g[a][b] = g[b][a] = dist;
}
cin>>cnt;
while(cnt--)
{
int q;cin>>q;
dijkstra(q);
int u = -1,mindist = 0x3f3f3f3f;
for(int i = n+1;i<=n+m;i++)
if(w[i]&&d[i]<mindist)mindist = d[i],u = i;
else if(w[i]&&d[i]==mindist&&w[i]>w[u])u = i;
else if(w[i]&&d[i]==mindist&&w[i]==w[u]&&num[i]<num[u])u = i;
w[u]--;
if(u==-1)puts("All busy");
else
{
vector<int>res;
for(int j = u;j!=q;j = pre[j])res.push_back(j);
res.push_back(q);
cout<<"A-"<<res[0]-n;
for(int i = 1;i<res.size();i++)
cout<<" "<<res[i];
cout<<endl;
cout<<d[u]<<endl;
}
}
return 0;
}
-----------------------------------------------------
//图中环的检测和标记，将访问过的多次的节点放入set中，如果要输出这个环，则对其中的一个点进行一次dfs即可
bool check_cycle(int u)
{
st[u] = true;
bool flag = true;
for (auto c : g[u])
{
if (st[c])cycle.insert(c),flag = false;
else flag &= check_cycle(c);
}
return flag;
}
int main()
{
cin >> n >> m;
while (m--)
{
int x, y; cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
check_cycle(1);
return 0;
}
-----------------------------------------------------
/*
（三）图的性质：模拟题&&阅读理解题---建议可以复习一下离散数学图论部分知识点
*/
/*
常考知识点：
环路：起点和终点相同
简单回路：每个点只访问一次
覆盖：所有顶点都被该条路径包含
*/
-----------------------------------------------------
/*
1.PAT-1122
哈密顿回路：哈密顿回路问题是找到一个包含图中每个顶点的简单回路。
分析定义可知条件有三：回路，包含所有顶点，该回路是简单回路
知识点：简单回路---->路径上经过的点只访问一次
包含每个顶点的回路即表示该序列组成了该图的一个遍历序列，组成了一个生成树
*/
const int N = 1010;
int g[N][N],seq[N],n,m;
set<int>s;
int main()
{
cin>>n>>m;
memset(g,0,sizeof g);
while(m--)
{
int x,y;cin>>x>>y;
g[x][y] = g[y][x] = 1;
}
int k;cin>>k;
while(k--)
{
int cnt;cin>>cnt;
bool flag = true;
set<int>c;
for(int i = 0;i<cnt;i++)cin>>seq[i];
for(int i = 0;i<cnt-1;i++)
{
int a = seq[i],b = seq[i+1];
c.insert(a),c.insert(b);
if(g[a][b]==0)flag = false;
}
if(seq[0]!=seq[cnt-1])puts("NO");//不是回路
else
{
if(c.size()!=n||n+1!=cnt)flag = false;//不是覆盖所有顶点的回路||不是简单回路
if(flag)puts("YES");
else puts("NO");
}
}
return 0;
}
//check()
//1.所有点访问 2.每一步都有边 3.起点终点相同 4.n+1
bool check(int cnt)
{
if(cnt!=n+1||Node[0]!=Node[cnt-1])return false;
memset(visit,0,sizeof visit);
for(int i = 0;i<cnt-1;i++)
{
visit[Node[i]] = true;
if(G[Node[i]][Node[i+1]]==false)return false;
}
for(int i = 1;i<=n;i++)
if(visit[i]==false)return false;
return true;
}
------------------------------------------
//PAT-1126 欧拉路径
/*
在图论中，欧拉路径是图中的一条路径，该路径满足恰好访问每个边一次。
而欧拉回路是一条在同一顶点处开始和结束的欧拉路径。
它们最早由欧拉于 1736 年解决著名的哥尼斯堡七桥问题时提出。
事实证明，如果一个连通图的所有顶点的度数都为偶数，那么这个连通图具有欧拉回路，且这个图被称为欧拉图。
如果一个连通图中有两个顶点的度数为奇数，其他顶点的度数为偶数，那么所有欧拉路径都从其中一个度数为奇数的顶点开始，并在另一个度数为奇数的顶点结束。
具有欧拉路径但不具有欧拉回路的图被称为半欧拉图。
现在，给定一个无向图，请你判断它是欧拉图、半欧拉图还是非欧拉图。
本题只需要得到每个顶点的度数即可，同时判断该图是连通的
*/
const int N = 1010;
int degree[N],p[N];
int find(int x)
{
return x==p[x]?x:p[x] = find(p[x]);
}
int main()
{
int n,m;cin>>n>>m;
int cnt = n;
for(int i = 1;i<=n;i++)p[i] = i;
while(m--)
{
int x,y;cin>>x>>y;
degree[x]++,degree[y]++;
int pa = find(x),pb = find(y);
if(pa!=pb)p[pa] = pb,cnt--;
}
int odd = 0,oven = 0;
for(int i = 1;i<=n;i++)
{
cout<<degree[i];
if(i!=n)cout<<" ";
if(degree[i]%2==0)oven++;
else odd++;
}
cout<<endl;
if(cnt!=1)puts("Non-Eulerian");
else
{
if(oven==n)puts("Eulerian");
else if(odd==2)puts("Semi-Eulerian");
else puts("Non-Eulerian");
}
return 0;
}
//PAT-1134 顶点覆盖---简单模拟，遍历边即可
//PAT-1154 顶点着色---简单模拟，遍历边，使用set统计颜色数目
---------------------------------------------
//PAT-1146 拓扑排序---模拟，遍历所有边，判断活动时间（理解为pos）是否符合顺序
int n,m;
const int N = 1010,M = 100100;
struct Edge{
int x,y;
}e[M];
int q[N],pos[N];
vector<int> res;
int main()
{
cin>>n>>m;
for(int i = 0;i<m;i++)cin>>e[i].x>>e[i].y;
int k;cin>>k;
for(int i = 0;i<k;i++)
{
for(int j = 0;j<n;j++)
{
cin>>q[j];
pos[q[j]] = j;
}
for(int j = 0;j<m;j++)
if(pos[e[j].x]>pos[e[j].y])//出现活动时间逆序的情况
{
res.push_back(i);
break;
}
}
for(int i = 0;i<res.size();i++)
{
cout<<res[i];
if(i!=res.size()-1)cout<<" ";
}
return 0;
}
//补充：拓扑排序代码：每次选择入度=0的点，加入栈中，每次弹出一个节点访问，对其所有邻边入度-1，
//然后检测入度=0的点则加入栈中
#include<iostream>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;
const int N = 110;
int n,m,count[N];
bool st[N];
vector<int>g[N],res;
stack<int>s;
void toposort()
{
memset(st,0,sizeof st);
while(!s.empty())
{
int top = s.top();
s.pop();
res.push_back(top);
st[top] = true;
for(auto c:g[top])
if(!st[c])
{
count[c]--;
if(count[c]==0)s.push(c);
}
}
}
int main()
{
cin>>n>>m;
memset(count,0,sizeof count);
for(int i = 0;i<m;i++)
{
int x,y;cin>>x>>y;
g[x].push_back(y),count[y]++;
}
for(int i = 1;i<=n;i++)if(count[i]==0)s.push(i);
toposort();
for(auto c:res)cout<<c<<" ";
cout<<endl;
}
//法二：使用dfs进行逆拓扑排序，注意这里的统计count是出度，而不是入度
#include<iostream>
#include<stack>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int n,m,start,count_[N];
bool st[N];
vector<int>g[N],res;
void dfs(int s)
{
if(count_[s]==0)//出度=0时遍历孩子然后递归
{
res.push_back(s);st[s] = true;
for(auto c:g[s])
{
count_[c]--;
if(count_[c]==0)dfs(c);//注意=0时才递归
}
}
}
int main()
{
cin>>n>>m;
memset(count_,0,sizeof count_);
for(int i = 0;i<m;i++)
{
int x,y;cin>>x>>y;
g[y].push_back(x),count_[x]++;
}
for(int i = 1;i<=n;i++)if(count_[i]==0)start = i;
dfs(start);
reverse(res.begin(),res.end());
for(auto c:res)cout<<c<<" ";
cout<<endl;
}
//拓扑排序和关键活动——求解关键活动就在于每次更新邻边的入度的时候，更新一下这个点活动的最早开始时间
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N = 110;
int n, m,ingree[N],g[N][N],f[N];
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m--)
{
int x, y,d;
cin >> x >> y >> d;
g[x][y] = d;
ingree[y]++;
}
queue<int>q;
for (int i = 0; i < n; i++)if (ingree[i] == 0)q.push(i);
int last = 0,cnt = 0;
while (!q.empty())
{
int t = q.front();
cnt++;
q.pop();
for (int i = 0; i < n; i++)
if (g[t][i]!=0x3f3f3f3f)
{
f[i] = max(f[t] + g[t][i], f[i]);
last = max(last, f[i]);
ingree[i]--;
if (ingree[i] == 0)q.push(i);
}
}
if (cnt != n)cout << "Impossible";
else cout << last << endl;
return 0;
}
//关键路径就是f[i] = e[i] (事件的最早开始时间和最迟开始时间组成的路径)
/*
拓扑排序后的序列，变成一个链状结构，位置在后的点只可能被前面的点连通
故若求每个点连通
*/
//ACwing -164 可达性统计
//直接dfs--显然会超时，因为询问次数较多，每次遍历平均访问n
#include<iostream>
#include<unordered_map>
#include<vector>
#include<cstring>
using namespace std;
const int N = 10010;
int n,m;
bool st[N];
vector<int> g[N];
int dfs(int u)
{
int cnt = 1;
st[u] = true;
for(auto c:g[u])
if(!st[c])cnt+=dfs(c);
return cnt;
}
int main()
{
cin>>n>>m;
while(m--)
{
int x,y;cin>>x>>y;
g[x].push_back(y);
}
for(int i = 1;i<=n;i++)
{
memset(st,0,sizeof st);
cout<<dfs(i)<<endl;
}
return 0;
}
//拓扑排序&位运算
/*
可达性统计
https://www.acwing.com/problem/content/166/
排成一条链之后，从后向前，前面的节点是其孩子节点的可达节点的并，因此这里采用可达即建边的方式（类似地铁线路）
这里存在问题在于若使用递推，则必须要记录其孩子节点的所有可达节点，否则可达节点会多次包含
（与dfs不同，dfs每一次都把st数组清空，因此是正确的，但是时间复杂度高）
这里如果使用f[N][N],则会导致空间不够，这里使用STL-bitset,每个位置只占1bit，而不是int的32bit
因此空间可以接受，使用bitset还有一个好处，就是在数孩子节点的时候，不需要使用统计个数（即不需要遍历）
bitset内置的函数维护1的个数---bitset 的介绍见STL相关内容
*/
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<bitset>
using namespace std;
const int N = 30010;
int n,m;
int d[N],seq[N];
vector<int> g[N];
bitset<N> f[N];
int topsort()
{
queue<int>q;
for(int i = 1;i<=n;i++)
if(d[i]==0)q.push(i);
int k = 0;
while(!q.empty())
{
int top = q.front();
q.pop();
seq[k++] = top;
for(auto c:g[top])
if(--d[c]==0)q.push(c);
}
}
int main()
{
scanf("%d %d",&n,&m);
memset(d,0,sizeof d);
while(m--)
{
int x,y;
scanf("%d %d",&x,&y);
g[x].push_back(y);
d[y]++;
}
topsort();
for(int i = n-1;i>=0;i--)
{
int t = seq[i];
f[t][t] = 1;
for(auto c:g[t])
f[t]|=f[c];
}
for(int i = 1;i<=n;i++)printf("%d\n",f[i].count());
return 0;
}
-----------------------------------------------
//PAT-1150 旅行商问题---阅读理解&&模拟
/*
TS simple cycle，如果这是一个访问每个城市的简单回路。---cnt==n+1 && num==n
TS cycle，如果这是一个访问每个城市的回路，但不是简单回路。---cnt!=n+1 && num==n
Not a TS cycle，如果这不是一个访问了每个城市的回路。---num!=n
*/
int n,m;
const int N = 210;
int g[N][N];
int main()
{
cin>>n>>m;
while(m--)
{
int x,y,z;cin>>x>>y>>z;
g[x][y] = g[y][x] = z;
}
int k;cin>>k;
int mindist = 0x3f3f3f3f,minid = 0;
for(int i = 1;i<=k;i++)
{
int cnt;cin>>cnt;
vector<int>seq;
for(int j = 0;j<cnt;j++)
{
int x;cin>>x;
seq.push_back(x);
}
int dist = 0;
set<int>s;
for(int j = 0;j<cnt-1;j++)
{
int u = seq[j],v = seq[j+1];
s.insert(u),s.insert(v);
if(g[u][v]==0)
{
dist = -1;
break;
}
else dist+=g[u][v];
}
if(dist==-1)printf("Path %d: NA (Not a TS cycle)\n",i);
else
{
if(seq[0]!=seq[seq.size()-1])
printf("Path %d: %d (Not a TS cycle)\n",i,dist);
else
{
if(s.size()==n)
{
if(dist<mindist)mindist = dist,minid = i;
if(cnt==n+1)
printf("Path %d: %d (TS simple cycle)\n",i,dist);
else printf("Path %d: %d (TS cycle)\n",i,dist);
}
else printf("Path %d: %d (Not a TS cycle)\n",i,dist);
}
}
}
printf("Shortest Dist(%d) = %d",minid,mindist);
return 0;
}
-----------------------------------------------------------------
/*
最小生成树问题：贪心策略
1）收n-1条边
2）无回路
Prim 算法：小树长大
*/
/*习题8.4 畅通工程之最低成本建设问题 (30分)
某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，
并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通
（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。
现得到城镇道路统计表，表中列出了有可能建设成快速路的若干条道路的成本，求畅通工程需要的最低成本。
*/
//prim算法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1001;
int dist[N],g[N][N],p[N],n,m;
bool st[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for(int i = 0; i < n; i ++)
{
int t = -1;
for(int j = 1; j <= n; j ++)
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if(i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
if(i) res += dist[t];
st[t] = true;
for(int j = 1; j <= n; j ++) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
while(m--)
{
int x,y,z;cin>>x>>y>>z;
g[x][y] = g[y][x] = z;
}
int res = prim();
if(res==0x3f3f3f3f)puts("Impossible");
else cout<<res<<endl;
return 0;
}
//采用kruskal算法，每次选择最短边，检测是否成环，但是下面的代码最后一个测试样例没过
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
vector<int>g[N];
int n,m;
bool st[N];
struct Edge
{
int x,y,z;
bool operator<(const Edge a)
{
return z<a.z;
}
}e[N*3];
int main()
{
cin>>n>>m;
for(int i = 0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
e[i] = {x,y,z};
}
sort(e,e+m);
memset(st,0,sizeof st);
int i = 0,cnt = 0,cost = 0,effect = 0;
while(i<m&&effect<n-1)
{
auto c = e[i];
int x = c.x,y = c.y,z = c.z;
if(st[x]&&st[y])i++;
else
{
if(!st[x])st[x] = true,cnt++;
if(!st[y])st[y] = true,cnt++;
cost+=z;
effect++;
}
}
if(effect==n-1)cout<<cost<<endl;
else puts("Impossible");
return 0;
}
//使用并查集维护图的连通性，求最小生成树的kruskal算法
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10100;
int n,m,p[N];
struct edge
{
int a,b,c;
bool operator < (const edge& t)const
{
return c<t.c;
}
}e[N];
int find(int x)
{
return x==p[x]?x:p[x] = find(p[x]);
}
int main()
{
cin>>n;int idx = 0,cnt = 0;
for(int i = 1;i<=n;i++)p[i] = i;
for(int i = 0;i<n*(n-1)/2;i++)
{
int a,b,c,d;cin>>a>>b>>c>>d;
if(d==0)e[idx++] = {a,b,c};
else
{
if(find(a)!=find(b))
cnt++,p[find(a)] = find(b);
}
}
sort(e,e+idx);
int res = 0;
for(int i = 0;i<idx;i++)
{
int a = e[i].a,b = e[i].b,c = e[i].c;
if(find(a)!=find(b))
cnt++,p[find(a)] = find(b),res+=c;
}
cout<<res<<endl;
return 0;
}
//连通最少费用，直接使用并查集
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10100;
int n,m,p[N];
struct edge
{
int a,b,c;
bool operator < (const edge& t)const
{
return c<t.c;
}
}e[N];
int find(int x)
{
return x==p[x]?x:p[x] = find(p[x]);
}
int main()
{
cin>>n;int idx = 0,cnt = 0;
for(int i = 1;i<=n;i++)p[i] = i;
for(int i = 0;i<n*(n-1)/2;i++)
{
int a,b,c,d;cin>>a>>b>>c>>d;
if(d==0)e[idx++] = {a,b,c};
else
{
if(find(a)!=find(b))
cnt++,p[find(a)] = find(b);
}
}
sort(e,e+idx);
int res = 0;
for(int i = 0;i<idx;i++)
{
int a = e[i].a,b = e[i].b,c = e[i].c;
if(find(a)!=find(b))
cnt++,p[find(a)] = find(b),res+=c;
}
cout<<res<<endl;
return 0;
}
//battle over cities
//并查集简单应用
//battle over cities hard version
/*
每次假设损坏一个城市，然后遍历与之无关的所有边，合并集合，
如果发现不连通，挑出可以建立边的前几名（这几条边不包含当前的城市，且这几条边使得剩余节点连通）
可以发现，如果在初始化上做一定转化，把边排好序，每次加入边的时候判断是否是损坏的边，更新费用
则可以变成一个最小生成树问题，测试样例4没过
*/
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 550,M = N*N/2;
int n, m;
struct edge
{
int x, y, d,s;
bool operator <(const edge a)const
{
if (a.s == s)
{
return d < a.d;
}
return s > a.s;
}
}e[M];
int p[N];
int find(int x)
{
return x == p[x] ? x : p[x] = find(p[x]);
}
int main()
{
cin >> n >> m;
int idx1 = 0, idx2 = 0;
for (int i = 0; i < m; i++)
{
int a, b, d, s;
cin >> a >> b >> d >> s;
e[i] = { a,b,d,s };
}
sort(e, e+m);
vector<int> res;
int maxcost = 0;
for (int i = 1; i <= n; i++)
{
int cnt = n-1,cost = 0;
for (int i = 1; i <= n; i++)p[i] = i;
for (int j = 0; j < m; j++)//遍历与i无关的边，检查是否连通
{
int x = e[j].x, y = e[j].y;
if (cnt == 1)break;
if (x == i || y == i)continue;
if (find(x) != find(y))
{
cnt--;
if (e[j].s == 0)cost += e[j].d;
p[find(x)] = find(y);
}
}
if (cnt > 1)res.clear(), res.push_back(i),maxcost = 0x3f3f3f3f;
if (cost != 0)
{
if (cost > maxcost)//更新最大距离
{
res.clear();
res.push_back(i);
maxcost = cost;
}
else if (cost == maxcost)//多个相同答案
res.push_back(i);
}
}
if (res.size())
{
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); i++)
{
cout << res[i];
if (i != res.size() - 1)cout << " ";
}
}
else cout << 0 << endl;
return 0;
}
------------------------------------------
/*
树的直径问题进阶
定义
树的直径的定义
在一棵树中，每一条边都有权值，树中的两个点之间的距离，
定义为连接两点的路径上边权之和，那么树上最远的两个点，他们之间的距离，就被称之为，树的直径。
树的直径的别称，树的最长链。请注意：树的直径，还可以认为是一条路径，不一定是只是一个数值。
*/
//例题：巡逻
/*
有一颗n−1n−1个节点的树,警察局设在根节点,两个节点之间的距离固定是11,
现在要求所有的节点都要至少访问一遍,可以访问多次.
猪八戒警察是个不愿意浪费多余时间的人死胖子,时间要花在睡觉吃饭上面,所以他只想要走最短的路.
要致富先修路,于是上面派发了巨款修路,这笔巨款,居然可以添加一条路,或者两条路.巨款好多啊,全被猪八戒买东西吃掉了
不过有要求,那就是新修建的路,只准走一次,因为豆腐渣工程,不安全.
题目关键：
1）巡逻的含义：每一条边都要走两次，因此总巡逻距离则是走完所有边的权值*2（即边数*2）
这里，添加一条路径就相当于贡献出一个环，这个环可以减少部分边走两次的行为
那么如何使得减少的访问的边数量更多呢（通过例子我们可以看出，走回边相当于间接求两个点的距离）
如果我们连接树直径的两端，则会减少访问的边数 = 树的直径-1
则巡逻开销变为 2*(n-1)-L+1
2）
偷懒走最少的路
换句话表示是什么?
不要走最长的路
什么是最长的路?
树的直径
树的直径是什么?
一棵树上,最远的两个点,他们的距离.
添加路径有什么效果?
使得两个点的最短距离变成11.
当只能增加一条新的路径的时候,我们怎么最大化利润?
找到树的直径的两个端点,在他们中间添加一条新路径.
*/
//树的直径求法：两次dfs搜索（或者bfs搜索），第一次选择任意一个点为起点，搜出最远的点
//第二次从这个最远的点搜出距离它最远的点，这两次搜索的结果就是树的直径两个端点
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, k,g[N][N],L = 0,p = 0,pre[N];
bool st[N];
//dfs求距离最远的点，并标记前驱数组
void dfs(int u,int deepth)
{
st[u] = true;
if (deepth > L)L = deepth, p = u;
for (int i = 1; i <= n; i++)
if (g[u][i]!=-1 && !st[i])
pre[i] = u,dfs(i, deepth + 1);
}
int main()
{
cin >> n >> k;
memset(g, -1, sizeof g);
for(int i = 0;i<n-1;i++)
{
int x, y; cin >> x >> y;
g[x][y] = g[y][x] = 1;
}
dfs(1,0);
int d1 = p;
L = 0;
memset(st, 0, sizeof st);
dfs(p, 0);
int d2 = p;
cout << L << endl;
for (int i = d2; i != d1; i = pre[i])cout << i << " ";
cout << d1 << endl;
return 0;
}
//以上是只增加一条路径的情况，PAT准备到这里也就足够了，
//下面是增加两条路径，需要修改两个重叠环的边权继续递归的
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, k,g[N][N],L = 0,p = 0,pre[N];
bool st[N];
void dfs(int u,int deepth)
{
st[u] = true;
if (deepth > L)L = deepth, p = u;
for (int i = 1; i <= n; i++)
if (g[u][i]!=0 && !st[i])
pre[i] = u,dfs(i, deepth + g[u][i]);
}
int main()
{
cin >> n >> k;
memset(g, 0, sizeof g);
for(int i = 0;i<n-1;i++)
{
int x, y; cin >> x >> y;
g[x][y] = g[y][x] = 1;
}
dfs(1,0);
int d1 = p;
L = 0;
memset(st, 0, sizeof st);
dfs(p, 0);
int d2 = p; int L1 = L;
int res = 2 * (n - 1) - (L1 - 1);
if(k==1)cout << res << endl;
else
{
for (int i = d2; i != d1; i = pre[d2])g[i][pre[i]] = g[pre[i]][i] = -1;
dfs(1, 0);
d1 = p;
memset(st, 0, sizeof st);
dfs(p, 0);
d2 = p; int L2 = L;
res = 2 * (n - 1) - (L1 - 1) - (L2 - 1);
cout << res << endl;
}
return 0;
}
/*
继续思考,树的直径显然不是唯一的，但是树的中心（直径的中点）是唯一的
即树的所有直径交于一个点
如果有时间继续探究，请完成树的偏心距练习
上述求树的直径问题，如果存在一个基环，则可以先扫描出这个基环，然后将其标记为广义的根节点
即标记的节点之间边权是0，这样像之前一样还是做两次dfs就可以解决问题
*/
很棒！！点赞收藏了！
加油！！