当前位置：首页 > article >正文

acm培训 part 7

article 2025/2/22 3:10:38

这部分的重点是图论

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;
}