Day14

2018-08-21

字数统计: 1.5k字 | 阅读时长: 8min

营救

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int fr,to,w;
}edge[1200010];
int n,m,s,t,fa[100100];
int find(int x)
{
	return (fa[x]==x)?x:fa[x]=find(fa[x]);
}
inline int cmp(node a,node b)
{
	return a.w<b.w;
}
inline int kru()
{
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		
		int v=edge[i].to,u=edge[i].fr;
		int fu=find(u),fv=find(v);
		if(fu==fv) continue;
		if(fu<fv)fa[fv]=fu;
		if(fu>fv)fa[fu]=fv;
		int fs=find(s),ft=find(t);
		if(fs==ft) return edge[i].w;
	}
}
int main()
{
	freopen("first.in","r",stdin);
	freopen("first.out","w",stdout);
	scanf("%d %d %d %d",&n,&m,&s,&t);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&edge[i].fr,&edge[i].to,&edge[i].w);
	}
	cout<<kru()<<endl;
}

觉得这道题就是一道裸的最小生成树题，将边排序，从小到大加边直到s和t在同一个集合内。

小D的地下温泉

#include<bits/stdc++.h>
using namespace std;
const int N = 1000100;
char s[N];
int fa[N*2],cnt,w[N*2];
int m,n;
int find(int x)
{
	return fa[x]?fa[x]=find(fa[x]):x;
}
int d[N];
void get(int i,int j)
{
	if(s[i*m+j]=='*'||d[i*m+j]) return;
	++w[d[i*m+j]=cnt];
	if(i+1<n) get(i+1,j);
	if(j+1<m) get(i,j+1);
	if(j) get(i,j-1);
	if(i) get(i-1,j);
}
void merge(int x,int y,int x1,int y1)
{
	int f1=find(d[x*m+y]),f2=find(d[x1*m+y1]);
	if(s[x1*m+y1]=='*'||f1==f2) return;
	w[f2]+=w[f1];
	w[f1]=0;
	fa[f1]=f2;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
	scanf("%s",s+i*m);
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)
		if(s[i*m+j]=='.'&&!d[i*m+j]) ++cnt,get(i,j);
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int opt,k,ans=1,mx=0;
		scanf("%d%d",&opt,&k);
		for(int j=1;j<=k;j++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			x--;y--;
			if(opt==1)
			{
				if(s[x*m+y]=='*') continue;
				int f=find(d[x*m+y]);
				if(mx<w[f]) mx=w[f],ans=j;
			}
			if(opt==2)
			{
				if(s[x*m+y]=='.')
				{
					int f=find(d[x*m+y]);
					s[x*m+y]='*';
					d[x*m+y]=0;
					w[f]--;
				}
				else 
				{
					s[x*m+y]='.';
					w[d[x*m+y]=++cnt]++;
					if(x) merge(x,y,x-1,y);
					if(y) merge(x,y,x,y-1);
					if(x+1<n) merge(x,y,x+1,y);
					if(y+1<m) merge(x,y,x,y+1);
				}
			}
		}
		if(opt==1) printf("%d\n",ans);
	}
	return 0;
}

题解;

个人认为这道题是最恶心的，想出正解后，调代码用了快两个小时qwq.
首先，把每一个联通快当成一个点，记录个数(cnt)。对于操作二，分情况讨论，若是温泉，该联通块大小减一，若不是温泉，查找四周温泉，进行合并。

炸

 (destroy.pas/c/cpp) 
【问题描述】
有n个星球，这些星球被m个双向通行的传送通道连接，传送依次需要的时间为1
现在坏人占领了这些星球，想要切断其中的联系，于是坏人决定把一些通道炸掉
但是坏人为了对付好人，还要进行军队运输和物资运输，于是坏人想知道，在保证从星球s1到星球t1所需时间不超过l1，从s2到t2不超过l2的情况下，最多能炸几座桥
【输入】
一行两个空格隔开的整数n,m，城市从1到n编号
接下来m行，每行两个空格隔开的整数l,r，保证两个星球中最多只有一条路
最后两个每行三个空格隔开的整数，分别表示s1,y1,l1和s2,y2,l2
【输出】
一行一个整数表示你的答案
如果无解输出-1
【输入输出样例1】
5 4 
1 2 
2 3 
3 4 
4 5 
1 3 2 
2 4 2	


1

【数据范围】 
20% n,m<=15
20% m=n-1
20% s1=s2,t1=t2
20% s1=s2
100% 1<=n,m<=3000,1<=u,v<=n,u!=v,1<=s1,s2,t1,t2<=n,0<=li<=n

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dis[3100][3100];
vector<int> to[3100];
void bfs(int x)
{
	queue<int> q;
	q.push(x);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<to[u].size();i++)
		{
			int v=to[u][i];
			if(dis[x][v]!=-1) continue;
			dis[x][v]=dis[x][u]+1;
			q.push(v);
		}
	}
}
int main()
{
	freopen("destroy.in","r",stdin);
	freopen("destroy.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(dis,-1,sizeof(dis));
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		to[u].push_back(v);
		to[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		dis[i][i]=0;
		bfs(i);
	}
	int s1,t1,l1,s2,t2,l2,ans=0,tmp,tmp1,tmp2;
	scanf("%d%d%d",&s1,&t1,&l1);
	scanf("%d%d%d",&s2,&t2,&l2);
	if(dis[s1][t1]>l1)
	{
		printf("-1\n");
		return 0;
	}
	if(dis[s2][t2]>l2)
	{
		printf("-1\n");
		return 0;
	}
	ans=dis[s1][t1]+dis[s2][t2];
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
	{
		tmp=dis[s1][i]+dis[s2][i]+dis[i][j]+dis[j][t1]+dis[j][t2];
		tmp1=dis[s1][i]+dis[i][j]+dis[j][t1];
		tmp2=dis[s2][i]+dis[i][j]+dis[j][t2];
		if(tmp1<=l1&&tmp2<=l2&&tmp<ans) ans=tmp;
		tmp=dis[s1][i]+dis[s2][j]+dis[i][j]+dis[j][t1]+dis[i][t2];
		tmp2=dis[s2][j]+dis[i][j]+dis[i][t2];
		if(tmp1<=l1&&tmp2<=l2&&tmp<ans) ans=tmp;
	}
	cout<<m-ans<<endl;
	return 0;
}

题tu解cao

这道题用两遍最短路可得65分的好成绩，然而这并不是正解，我一开始以为只能得40分部分分qwq.
因为所有的边长都为1，并且1<=n,m<=3000，所以可以用bfs和数组算出每两个点之间的距离。然后枚举两条边之间的公共部分更新答案。

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/5402392a.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！