acm培训part7

这部分的重点是图论

1.题目解析 1.1 Stockbroker Grapevine

这道题的重点是通过图建立各个经纪人之间的关系，再存储传播所需要的值。通过不断模拟去找到所需要的最短时间，代码如下

#include<bits/stdc++.h> using namespace std; const int INF=1000000000; const int maxn=100+5; int dist[maxn][maxn]; int G[maxn][maxn]; int func(int n) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(G[i][j]==0) dist[i][j]=INF; else dist[i][j]=G[i][j]; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); } bool solve(int n) { int MinT=INF,MaxT,Max; int pMin,rMax; for(int i=1;i<=n;i++) { int sum=0,MaxT=0; for(int j=1;j<=n;j++) { if(i==j) continue; sum+=dist[i][j]; if(dist[i][j]>MaxT){ MaxT=dist[i][j]; } if(sum>MinT) break; } if(MinT>sum) { pMin=i; MinT=sum; Max=MaxT; } } if(MinT>=INF) return false; cout<<pMin<<' '<<Max<<endl; return true; } int main() { int n,u,v,w,m; while(cin>>n,n) { memset(G,0,sizeof(G)); for(int u=1;u<=n;u++) { cin>>m; while(m--) { cin>>v>>w; G[u][v]=w; } } func(n); if(!solve(n)) cout<<"disjoint"<<endl; } return 0; } 1.2 树的直径

#include<bits/stdc++.h> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 500000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; struct Edge{ int w; int from,to; int next; }edge[N]; int head[N],edgeNum=0; int n,m; int dis[N*2]; bool vis[N]; int start,endd; void addEdge(int from,int to,int w) { edge[++edgeNum].to=to; edge[edgeNum].w=w; edge[edgeNum].next=head[from]; edge[edgeNum].from=from; head[from]=edgeNum; } void dfs(int x) { vis[x]=true; for(int i=head[x];i!=-1;i=edge[i].next){ int to=edge[i].to; if(!vis[to]) { dis[to]=dis[x]+edge[i].w; dfs(to); } } } int main() { scanf("%d",&n); memset(head,-1,sizeof(head)); edgeNum=0; m=n-1; for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); addEdge(x,y,1); addEdge(y,x,1); } memset(vis,false,sizeof(vis)); memset(dis,INF,sizeof(dis)); dis[1]=0; dfs(1); int maxx=-INF; for(int i=1;i<=n;i++){ if(dis[i]>maxx&&dis[i]!=INF) { maxx=dis[i]; start=i; } } memset(vis,false,sizeof(vis)); memset(dis,INF,sizeof(dis)); dis[start]=0; dfs(start); maxx=-INF; for(int i=1;i<=n;i++){ if(dis[i]>maxx&&dis[i]!=INF) { maxx=dis[i]; endd=i; } } printf("%d\n",maxx); return 0; } 1.3 Invitation Cards

这道题的重点是通过顶点和边的定义，实现了从起点到所有其他顶点的最短路径计算，并最终输出总路径长度，代码如下

#include<bits/stdc++.h> #define N 1000010 #define LL long long using namespace std; const int inf = 0x3f3f3f3f; int head[N], head1[N], cnt, cnt1; int dist[N], vis[N]; struct node { int v, s, nxt; }e[N], re[N]; struct Node { int v, d; Node(int v1, int d1) { v = v1; d = d1; } bool operator < (const Node& w)const { return d > w.d; } }; void add(int u, int v, int s) { e[++cnt].v = v; e[cnt].s = s; e[cnt].nxt = head[u]; head[u] = cnt; } void add1(int u, int v, int s) { re[++cnt1].v = v; re[cnt1].s = s; re[cnt1].nxt = head1[u]; head1[u] = cnt1; } void dijkstra() { memset(dist, inf, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[1] = 0; priority_queue<Node> q; q.push(Node(1, 0)); int t; while (!q.empty()) { t = q.top().v; q.pop(); if (vis[t])continue; vis[t] = 1; for (int i = head[t]; i; i = e[i].nxt) { int v = e[i].v, s = e[i].s; if (!vis[v] && dist[v] > dist[t] + s) { dist[v] = dist[t] + s; q.push(Node(v, dist[v])); } } } } int main() { int t; scanf("%d", &t); while (t--) { int p, q; int u, v, s; cnt = cnt1 = 0; memset(head, 0, sizeof(head)); memset(head1, 0, sizeof(head1)); scanf("%d%d", &p, &q); while (q--) { scanf("%d%d%d", &u, &v, &s); add(u, v, s); add1(v, u, s); } int ans = 0; dijkstra(); for (int i = 1; i <= p; i++) { ans += dist[i]; } memcpy(head, head1, sizeof(head1)); memcpy(e, re, sizeof(re)); dijkstra(); for (int i = 1; i <= p; i++) { ans += dist[i]; } printf("%d\n", ans); } return 0; } 1.4 战略游戏

这里的重点对于每个节点,我们都把它当成根节点处理，因为是一棵树,所以对于每个节点,我们都把它当成根节点处理，对于每个节点,我们都把它当成根节点处理，代码如下

#include<bits/stdc++.h> using namespace std; const int N=1500+10; vector<int>v[N]; int n,x,k,id,fa[N],f[N][2],ans=1<<30; void dfs(int u){ f[u][1]=1; for(int i=0;i<v[u].size();i++){ int son=v[u][i]; dfs(son); f[u][1]+=min(f[son][0],f[son][1]); f[u][0]+=f[son][1]; } } void solve() { cin>>n; for(int i=1;i<=n;i++){ cin>>id>>k; while(k--){ cin>>x; v[id].push_back(x); fa[x]=true; } } for(int i=0;i<n;i++){ if(fa[i]==false){ memset(f,0,sizeof f); dfs(i); ans=min(ans,min(f[i][1],f[i][0])); } } cout<<ans<<"\n"; } int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); solve(); return 0; } 2. 学习总结

无向图

1.两个顶点之间如果有边连接，那么就视为两个顶点相邻

2. 路径：相邻顶点的序列

3. 圈：起点和终点重合的路径

4. 连通图：任意两点之间都有路径连接的图

5. 度：顶点连接的边数叫做这个顶点的度

6. 树：没有圈的连通图

7. 森林：没有圈的非连通图

有向图

1.在有向图中，边是单向的：每条边所连接的两个顶点是一个有序对，他们的邻接性是单向的

2. 有向路径：相邻顶点的序列

3. 有向环：一条至少含有一条边且起点和终点相同的有向路径

4. 有向无环图：没有环的有向图

5. 度：一个顶点的入度与出度之和称为该顶点的度 入度：以顶点为弧头的边的数目称为该顶点的入度 出度：以顶点为弧尾的边的数目称为该顶点的出度

图的遍历：从图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。为了保证图中的顶点在遍历过程中仅访问一次，要为每一个顶点设置一个访问标志

欧拉路指的是：存在这样一种图，可以从其中一点出发，不重复地走完其所有的边如果欧拉路的起点与终点相同，则称之为欧拉回路‘

满足的条件

1.图是连通的，若不连通不可能一次性遍历所有边

2. 对于无向图：有且仅有两个点，与其相连的边数为奇数，其他点相连边数皆为偶数；或所有点皆为偶数边点。对于两个奇数点，一个为起点，一个为终点。起点需要出去，终点需要进入，故其必然与奇数个边相连

3. 如果存在这样一个欧拉路，其所有的点相连边数都为偶数，那说明它是欧拉回路

4. 对于有向图：除去起点和终点，所有点的出度与入度相等。起点出度比入度大1，终点入度比出度大1。若起点终点出入度也相同，则为欧拉回路