c++练习7（图论）_图论 编程题 c++
1.Stockbroker Grapevine
解题思路：
由于n的值较小，所以可以选择Floyd方法来求最短路。
代码：
#includeusing 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&&n!=0){ init(); int num,to,dis; for(int i=1;i>num; for(int j=1;j>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=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，求两次最远点时的两点间距离就是直径。
代码：
#includeusing namespace std;const int N=100005;vector 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>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#include#include#includeusing namespace std;typedef long long ll;const int N = 1000005;typedef pair 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, greater > 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, greater > 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 #include #include using namespace std;const int MAXN = 1505;vector 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 > u >> k; for (int j = 0; j > 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 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 b.dis; } }; priority_queue 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 函数，我们可以在遍历的同时记录下每个节点进出栈的时间序列。
