2021.9.28图论测试

100+8+100,还算过得去,虽然感觉有点遗憾,因为第二题死就死在了手一抖无向边只加了一次……

为了备战初赛,我已经一个月没有写过题了,所以这是9月真正意义上第一次写代码。手感还可以,虽然只能说是还可以。

这道题感觉不难。一开始以为好复杂的一道题,甚至以为要用上奇奇怪怪的什么图上DP,结果fang慌了半个小时以后,再去看那道题的题面,发现题面中的"X"是指前X个条件,而不是任意X个,于是乎当场自闭……

朴素算法就是一个一个模拟加边,然后 \(O(N)\) 验证,算法复杂度为 \(O(N^2)\) ;一开始的思路是优化验证部分,结果硬刚了半天毫无思路,结果灵光乍现,既然验证的 \(O(N)\) 优化不掉,那就可以考虑优化枚举部分啊,既然答案具有单调性(假如可以满足前i个,那么一定可以满足前i-1个),何不二分?

于是一个二分+拓扑验证的算法出现了,复杂度为 \(O(NlogN)\)。至于什么输出字典序最小的方案,加个优先队列就行了。

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
//#define zczc
using namespace std;
const int N=100010;
const int M=200010;
const int S=50010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); }
    wh*=f;return;
}

int m,n;//点数,结论数

struct edge{
	int t,next;
}e[M];
int esum,head[N];
inline void add(int fr,int to){
	esum++;
	e[esum].t=to;
	e[esum].next=head[fr];
	head[fr]=esum;
	return;
}//加边模板

vector<int>a[S];int d[N];
inline void get(int wh){
	int num,data;read(num);
	while(num--){
		read(data);
		a[wh].push_back(data);
	}
	return;
}
inline void addedge(int wh){
	for(int i=1;i<a[wh].size();i++){
		add(a[wh][i-1],a[wh][i]);
		d[a[wh][i]]++;
	}
	return;
}//信息处理

bool vis[N];
queue<int>q;
void init(int wh){
	esum=0;
	memset(head,0,sizeof(head));
	memset(vis,false,sizeof(vis));
	memset(d,0,sizeof(d));
	for(int i=1;i<=wh;i++)addedge(i);
	while(!q.empty())q.pop();
	return;
}
bool check(){
	int num=0;
	for(int i=1;i<=m;i++){
		if(d[i]==0)q.push(i);
	}
	while(!q.empty()){
		int now=q.front();q.pop();
		if(vis[now])return false;
		vis[now]=true;num++;
		for(int i=head[now];i;i=e[i].next){
			d[e[i].t]--;
			if(d[e[i].t]==0)q.push(e[i].t);
		}
	}
	return num==m;
}

struct node{
	int data;
};
bool operator <(node s1,node s2){
	return s2.data<s1.data;
}
priority_queue<node>pq;
void print(){
	for(int i=1;i<=m;i++){
		if(d[i]==0)pq.push((node){i});
	}
	while(!pq.empty()){
		int now=pq.top().data;pq.pop();
		printf("%d ",now);
		for(int i=head[now];i;i=e[i].next){
			d[e[i].t]--;
			if(d[e[i].t]==0)pq.push((node){e[i].t});
		}
	}
	return;
}

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	
	read(m);read(n);
	for(int i=1;i<=n;i++)get(i);
	int l=0,r=n,mid;
	while(l<r){
		mid=l+r+1>>1;
		init(mid);
		if(check())l=mid;
		else r=mid-1;
	}
	init(l);
	print();
	
	return 0;
}

题面很恶心,读得我想去洗胃。不过模拟了一下之后发现似乎没那么复杂,就是一个最小生成树嘛。

主要是我忘了加两次边了,郁闷。

#include<cstdio>
#include<cstring>
#include<algorithm>
//#define zczc
using namespace std;
const int N=100010*2;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); }
    wh*=f;return;
}

int m,w[N],a[N][4];
int c[N],sum;
namespace g{
	struct edge{
		int t,next;
	}e[N<<3];
	int head[N],esum;
	inline void add(int fr,int to){
		esum++;
		e[esum].t=to;
		e[esum].next=head[fr];
		head[fr]=esum;
	}
	void dfs(int wh,int color){
		//printf("c:%d %d\n",wh,color);
		c[wh]=color;
		for(int i=head[wh],th;i;i=e[i].next){
			th=e[i].t;
			if(c[th])continue;
			dfs(th,color);
		}
	}
	void solve(){
		int color=0;
		for(int i=1;i<=m*2;i++){
			if(c[i]==0){
				color++;
				//printf("w:%d %d\n",color,i);
				dfs(i,color);
			}
		}
		sum=color;
	}
}
namespace t{
	int f[N];
	inline int find(int wh){
		if(f[wh]==wh)return wh;
		return f[wh]=find(f[wh]);
	}
	inline void he(int s1,int s2){
		int f1=find(s1),f2=find(s2);
		f[f1]=f2;
	}//并查集 
	struct edge{
		int s1,s2,v;
	}e[N<<3];
	inline bool cmp(edge s1,edge s2){
		return s1.v<s2.v;
	}
	int esum;
	void solve(){
		for(int i=1;i<=sum;i++)f[i]=i;
		//printf("%d\n",sum);
		for(int i=1;i<=m;i++){
			esum++;
			e[esum].s1=c[a[i][0]];
			e[esum].s2=c[a[i][2]];
			e[esum].v=w[i];
		}
		sort(e+1,e+esum+1,cmp);
		int ans=0;
		for(int i=1;i<=esum;i++){
			int n1=e[i].s1,n2=e[i].s2,nv=e[i].v;
			int f1=find(n1),f2=find(n2);
			if(f1==f2)continue;
			ans+=nv;
			he(n1,n2);
		}
		printf("%d",ans);
	}
}

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);
	for(int i=1;i<=m;i++){
		read(w[i]);
		for(int j=0;j<4;j++)read(a[i][j]);
		g::add(a[i][0],a[i][1]);
		g::add(a[i][1],a[i][0]);
		g::add(a[i][2],a[i][3]);
		g::add(a[i][3],a[i][2]);
	}
	g::solve();
	t::solve();
	
	return 0;
}

朴素算法加优化,还是可以做的。

#include<cstdio>
#include<queue>
#include<cstring> 
//#define zczc
#define int long long 
using namespace std;
const int N=50010;
const int M=100010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); }
    wh*=f;return;
}

int m,n,num;
struct edge{
	int t,v,next;
}e[M*3];
int esum,head[N];
inline void add(int fr,int to,int val){
	esum++;
	e[esum].t=to;
	e[esum].v=val;
	e[esum].next=head[fr];
	head[fr]=esum;
}

int tot,a[N],b[N];
struct node{
	int wh,dis;
};
bool operator <(node s1,node s2){
	return s2.dis<s1.dis;
}
priority_queue<node>q;
bool vis[N];
void dij(int wh,int dis[]){
	while(!q.empty())q.pop();
	memset(vis,false,sizeof(vis));
	for(int i=0;i<=m;i++)dis[i]=1e9;
	dis[wh]=0;q.push((node){wh,0});
	while(!q.empty()){
		node now=q.top();q.pop();
		int nwh=now.wh,nd=now.dis;
		if(vis[nwh])continue;vis[nwh]=true;
		for(int i=head[nwh],th;i;i=e[i].next){
			th=e[i].t;
			if(dis[nwh]+e[i].v<dis[th]){
				dis[th]=dis[nwh]+e[i].v;
				q.push((node){th,dis[th]});
			}
		}
	}
	return;
}

int dis0[N],dis1[N];

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	int s1,s2,s3;
	read(m);read(n);read(num);
	for(int i=1;i<=n;i++){
		read(s1);read(s2);read(s3);
		add(s1,s2,s3);add(s2,s1,s3);
	}
	for(int i=1;i<=num;i++){
		read(s1);read(s2);
		if(a[s1]==0)b[++tot]=s1;
		if(a[s1]<s2)a[s1]=s2;
	}
	dij(m,dis0);
	for(int i=1;i<=tot;i++){
		int now=b[i];
		add(0,now,dis0[now]-a[now]);
	}
	dij(0,dis1);
	for(int i=1;i<m;i++){
		if(dis0[i]>=dis1[i])printf("1\n");
		else printf("0\n");
	}
	
	return 0;
}
上一篇:大家这个点都还没睡吧| getchar的返回值为啥用int类型变量接收


下一篇:「POI2012」字母 Letters