1.Stockbroker Grapevine
解题思路：
由于n的值较小，所以可以选择Floyd方法来求最短路。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int G[N][N];
int n;
void init(){
memset(G,0x3f,sizeof(G));
for(int i=1;i<=n;i++){
G[i][i]=0;
}
}
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
G[i][j]=min(G[i][k]+G[k][j],G[i][j]);
}
}
}
}
int main(){
while(cin>>n&&n!=0){
init();
int num,to,dis;
for(int i=1;i<=n;i++){
cin>>num;
for(int j=1;j<=num;j++){
cin>>to>>dis;
G[i][to]=dis;
}
}
floyd();
int minTime=INT_MAX,startPerson=-1;
for(int i=1;i<=n;i++){
int maxTime=0;
bool isDisjoint=false;
//针对每个顶点，查看其到其他所有顶点的最短路径是否都小于无穷大,从而检查是否存在不连通点
for(int j=1;j<=n;j++){
if(G[i][j]>=0x3f3f3f3f){
isDisjoint=true;
break;
}
maxTime=max(maxTime,G[i][j]);
//找到从该顶点传播了所有点（人）的时间
}
if (!isDisjoint && maxTime < minTime) {
minTime = maxTime;
startPerson = i;
}//找到最短路线
}
if(startPerson==-1){
cout<<"disjoint"<<endl;
} else{
cout<<startPerson<<" "<<minTime<<endl;
}
}
return 0;
}
2.树的直径
解题思路：
树的数据结构，可以使用dfs序，随便定一个点x，求两次最远点时的两点间距离就是直径。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
vector<int> G[N];
int dis[N];//记录每个节点到起点的距离
int maxDisNode;//记录离起点最远的节点
int maxDis=0;//记录最大距离
void dfs(int x,int fa,int d){
dis[x]=d;
if(d>maxDis){
maxDis=d;
maxDisNode=x;
}//需要找到最远节点和距离
for(auto y:G[x]){
if(y==fa)continue;
dfs(y,x,d+1);
}
}
void add(int x,int y){
G[x].push_back(y);
}
int main(){
//存图
int n;
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);// 无向图需要双向添加边
}
dfs(1,0,0);
maxDis=0;
dfs(maxDisNode,0,0);
cout<<maxDis;
return 0;
}
3.Invitation Cards
解题思路：
本题要求计算所有志愿者从中央检查站（CCS，编号为 1）出发到各个站点，再从各个站点返回 CCS 的最小交通费用总和。可以将该问题拆分为两个子问题：计算从 CCS 到各个站点的最小费用和从各个站点返回 CCS 的最小费用，最后将这两部分费用相加。为了解决这两个子问题，可以使用 Dijkstra 算法来计算单源最短路径.
代码：
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1000005;
typedef pair<int, int > PAIR;
struct Edge{
int to;
int price;
int next;
};
Edge G[N],rG[N];
int head1[N],head2[N];
ll dis[N];
void spfa(){
memset(dis,0x3f,sizeof(dis));
priority_queue<PAIR, vector<PAIR>, greater<PAIR> > que;
que.push(PAIR(0,1)); dis[1] = 0;
while(!que.empty()){
int u = que.top().second;
que.pop();
for(int i = head1[u];i; i = G[i].next){
Edge e = G[i];
if(dis[e.to] > dis[u] + e.price){
dis[e.to] = dis[u] + e.price;
que.emplace(dis[e.to],e.to);
}
}
}
}
void spfa2(){
memset(dis,0x3f,sizeof(dis));
priority_queue<PAIR, vector<PAIR>, greater<PAIR> > que;
que.push(PAIR(0,1)); dis[1] = 0;
while(!que.empty()){
int u = que.top().second;
que.pop();
for(int i = head2[u];i; i = rG[i].next){
Edge e = rG[i];
if(dis[e.to] > dis[u] + e.price){
dis[e.to] = dis[u] + e.price;
que.emplace(dis[e.to],e.to);
}
}
}
}
int main(){
int n,p,q;
scanf("%d",&n);
while(n–){
memset(head1,0,sizeof(head1));
memset(head2,0,sizeof(head2));
scanf("%d%d",&p,&q);
for(int i = 1; i <= q; ++i){
int from,to,price;
scanf("%d%d%d",&from,&to,&price);
Edge e = {to,price,0};
G[i] = e;
G[i].next = head1[from];
head1[from] = i;
e.to = from;
rG[i] = e;
rG[i].next = head2[to];
head2[to] = i;
}
ll ans = 0;
spfa();
for(int i = 2; i <= p; ++i) ans += dis[i];
spfa2();
for(int i = 2; i <= p; ++i) ans += dis[i];
printf("%lld\\n", ans);
}
return 0;
}
4. 战略游戏
解题思路：
我们的目标是在树的节点上放置最少数量的士兵，使得树中的每条边都能被至少一个士兵瞭望到。可以将这个问题转化为在树的每个节点上进行状态转移，通过动态规划的思想来求解。
代码：
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1505;
vector<int> G[MAXN]; // 邻接表存储树
int dp[MAXN][2]; // dp数组，dp[u][0] 表示u不放置士兵，dp[u][1] 表示u放置士兵
// 树形DP函数
void dfs(int u, int fa) {
dp[u][0] = 0;
dp[u][1] = 1;
for (int v : G[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u][0] += dp[v][1];
dp[u][1] += min(dp[v][0], dp[v][1]);
}
}
int main() {
int n;
cin >> n;
// 构建树的邻接表
for (int i = 0; i < n; i++) {
int u, k;
cin >> u >> k;
for (int j = 0; j < k; j++) {
int v;
cin >> v;
G[u].push_back(v);
G[v].push_back(u); // 无向边
}
}
// 从任意节点开始DFS，这里选择节点0
dfs(0, -1);
// 最终答案是根节点放置或不放置士兵的最小值
int ans = min(dp[0][0], dp[0][1]);
cout << ans << endl;
return 0;
}
学习总结：
1.存图
邻接矩阵：
我们用一个 的二维数组来存储一个图，存储规则：若x 能到达y ，那么(x,y) 代表的就是x 到 y的距离，如果无法访问，我们用 -1或很大的数来表示。特别地，自己到自己的距离为0
int G[N][N];
void add(int x,int y) {
G[x][y] = 1;
}
void init() {
//初始化整张图
memset(G,0x3f,sizeof G);//当 sizeof 后面接的是表达式或者变量名时，括号是可选的。当 sizeof 后面接的是类型名时，必须使用括号。
for (int i = 1;i <= n;++i) G[i][i] = 0;
}
//遍历全图
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= n;++j) {
if (i == j) continue;
}
}
邻接矩阵只适用于没有重边（或重边可以忽略）的情况。其最显著的优点是可以 查询一条边是否存在。由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图(边比点多很多)上使用邻接矩阵.
邻接表(本质上是个链表) :
vector <int> G[N];
//如果需要存带边权的用 pair 就可以啦！
void add(int x,int y) {
G[x].push_back(y);
}//加边
for (int y : G[x]){
}//遍历x连出的所有边
2.最短路
Floyd:
枚举中转节点 。检查由 点经过此点到 点的路径是否比原先优。更新由 点到 点的最短距离.
void Floyd() {
for (int k = 1;k <= n;++k) {
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= n;++j) {
f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
}
}
}
}//时间复杂度O(N^3)
Dijkstra:
将顶点划为两堆，起初第一堆只有起点 这一个点。每次从第二堆里距离 点最近的点（这就是贪心了）取出，放入第一堆中，并更新最短路，直到第二堆中没有节点为止。Dijkstra 只能处理正权边。
int n,m,s,dis[N];
bool vis[N];
的时间复杂度：也就是步骤 2
struct node {
int pos,dis;
friend bool operator < (const node &a,const node &b) {//运算符函数是一种特殊的函数，它允许我们为自定义的数据类型（如类、结构体）重新定义运算符的行为。
return a.dis > b.dis;
}
};
priority_queue <node> q;//
void Dijkstra(int s) {
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
q.push((node){s,dis[s] = 0});
while (!q.empty()) {
node p = q.top();q.pop();
int x = p.pos;
if (vis[x]) continue;
vis[x] = 1;
for (auto e : G[x]) {
int y = e.first,w = e.second;
if (dis[y] > dis[x] + w) {
dis[y] = dis[x] + w;
q.push((node){y,dis[y]});
}
}
}
}//O(nlog n)
3.DFS序
深度优先搜索是一种用于遍历或搜索树或图的算法。该算法沿着树的深度遍历树的节点，尽可能深地搜索树的分支。
void dfs(int x,int fa) {
dfn[x] = ++cnt;
for (auto y : G[x]) {
if (y == fa) continue;
dfs(y,x);
}
}
树是一种非线性的数据结构，它的一些数据调用肯定是没有线性结构来得方便的。所以基于 DFS 函数，我们可以在遍历的同时记录下每个节点进出栈的时间序列。
