P3629 [APIO2010]巡逻

标签：https   fss   注意   tin   max   --   cst   continue   std   

Miku

很好的坑题，务必注意因为负边权和求路径的问题，这里需要同时用到两种方法，搜索和dp。

对于原来的情况，事实上就是每一条边都要走两次，（毕竟你还要回来啊）

但是你要是建了一条边，就会形成一个环，那么这辆车就可以直接走回去了（沿着这个圈回到出发点，也就是说，少了一条边长度的距离）

那么怎么搞呢，当然是Ko no 直径啊

建第二条边怎么搞呢？倘若说没有重叠部分，那么就是找呗

但是有重叠怎么办？

有重叠的边重叠部分不但不能少走，反而还要多走啊，这样的话，事实上“贡献”（是对减少长度的贡献）是个-1

所以说把第一次的直径取反就行了。

#include
#include
#include
#include
#include
int ans;
using namespace std;
int q[100001];
int pp;
int n,k;
int l,r;
int temx;
int dis[100001];
int vis[100001];
int dp[100001];
int ma[160][160] ;
struct b{
	int f;
	int to;
	int ne;
	int v;
}ed[200001];
int x,y;
int p;
int head[100001];
void add(int f,int to,int v){
	p++;
	ed[p].f=f;
	ed[p].to=to;
	ed[p].ne=head[f];
	ed[p].v=v;
	head[f]=p;
	return ;
}
void maxx(int x){
	if(dis[x]>dis[temx]){
		temx=x;
	}
	return ; 
}
void emp(){
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	temx=0;
	return ;
}
void dfs(int now,int f){
	vis[now]=1;
	for(int i=head[now];i;i=ed[i].ne){ 
 		if(vis[ed[i].to]==1)
 		continue;
 		dis[ed[i].to]=dis[now]+ed[i].v;
 		maxx(ed[i].to);
		dfs(ed[i].to,now);
	 } 
	return ;
}
int ff;
void dfss(int now,int f){
	vis[now]=1;
	q[++pp]=now;
	if(now==r||ff){
		ff=1;
		return ;
	}
	for(int i=head[now];i;i=ed[i].ne){ 
	 	if(vis[ed[i].to]==1||ff)
 		continue;
 		dis[ed[i].to]=dis[now]+ed[i].v;
		dfss(ed[i].to,now);
	} 
	if(!ff)
	pp--;
	return ;
}
void deal(){
	 for(int i=1;i

P3629 [APIO2010]巡逻

标签：https   fss   注意   tin   max   --   cst   continue   std   

原文地址：https://www.cnblogs.com/For-Miku/p/13832301.html