只有sort能a这题吗?
  • 板块P1656 炸铁路
  • 楼主jianglige
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/12/4 22:47
  • 上次更新2023/11/3 22:53:51
查看原帖
只有sort能a这题吗?
498531
jianglige楼主2021/12/4 22:47

第一遍不知道为何sort写炸了,改用优先队列,只得了60分,不知道应该怎么改

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

inline int read(){
	char c;int res=0,f=1;
	while(c=getchar(),!isdigit(c)) if(c=='-') f*=-1;
	while(isdigit(c)) res=res*10+c-'0',c=getchar();
	return res*f;
}
const int maxn=5005;
const int M=155;
int n,m;
int a[M],b[maxn],to[maxn],hd[maxn],nxt[maxn];
struct edge{
	int u,v;
}E[maxn];
priority_queue<edge,vector<edge>,greater<edge> > q;
int cnt=1;
void add_edge(int u,int v){
	to[++cnt]=v;
	nxt[cnt]=hd[u];
	hd[u]=cnt;
}
inline bool operator>(edge x,edge y)
	{return x.u>y.u;}
int dfn[maxn],low[maxn],ct,ct2;
void dfs(int u,int w){
	dfn[u]=low[u]=++ct;
	for(int i=hd[u];i;i=nxt[i]){
		int _v=to[i];
		if(!dfn[_v]){
			dfs(_v,i);
		  low[u]=min(low[u],low[_v]);
		  if(low[_v]>dfn[u]){
		  	 if(_v<u) E[++ct2].u=_v,E[ct2].v=u,q.push(edge{_v,u});
		  	 else E[++ct2].u=u,E[ct2].v=_v,q.push(edge{u,_v});
		  }
		}
	 else if(i!=(w^1)){
	 	low[u]=min(low[u],dfn[_v]);
	 }	 
	}
}
int main(){
     n=read();
     m=read();
     for(int i=1;i<=m;i++){
     	int u,v;
     	u=read();
     	v=read();
     	add_edge(u,v);
     	add_edge(v,u);
	}
	dfs(1,2);
    while(!q.empty()){
    	edge tmp=q.top();
    	q.pop();
    	cout<<tmp.u<<" "<<tmp.v<<endl;
	}
	return 0;
}

使用优先队列只对结构体中的u进行从小到大排序,对于v的排序不知道dalao们有没有实现方法

2021/12/4 22:47
加载中...