【Codeforces 788C】The Great Mixing

相关链接

题目传送门:http://codeforces.com/contest/788/problem/C
官方题解:http://codeforces.com/blog/entry/51312

解题报告

假设取$x$个物品的时候原问题有解,且第$i$个物品的编号为$b_i$
那么此时满足这个等式:$\sum\limits_{i=1}^{x}{a_{b_i}}=nx$

这个看起来既不满足单调性,又不能方便地$DP$
但如果我们把$n$给减到$a_i$里去,那么就是$\sum\limits_{i=1}^{x}{a_{b_i}}=0$
这个就好办了,直接搞一个$O(n^2)$的那个$BFS$

这个技巧应用较为广泛,还有一些升级版本
比如这个题:http://oi.cyo.ng/?p=3069

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;
const int M = 2000009;
const int BAS = 1000;

int n,m,tot,dis[N],head[N];
int nxt[M],to[M],_hash[M];
queue<int> que;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read(); m = read();
	for (int i=1;i<=m;i++) _hash[++tot] = read() - n;
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=tot;i++) {
		dis[_hash[i] + BAS] = 1;
		que.push(_hash[i] + BAS);
	} 
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=1,t;t=w+_hash[i],i<=tot;i++) {
			if (t < 0 || t > BAS*2 || dis[t]) continue;
			dis[t] = dis[w] + 1; que.push(t);
		}
	}
	cout<<(dis[BAS]?dis[BAS]:-1);
	return 0;
}

【BZOJ 2118】墨墨的等式

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2118
神犇题解:https://blog.sengxian.com/solutions/bzoj-2118

解题报告

先来看一道简单的题目:

给定$a,b,c(a,b,c \le 10^5)$,规定$x,y,z \in \mathbb{N}$
问$ax+by+cz$不能表示出的正整数中,最大的那一个是多少

我们不妨在$\bmod c$的意义下做,这样就可以只考虑$0 \sim c-1$
于是暴力用$a,b$连边,跑一边最短路
这样就可以求出在$\bmod c$的剩余系中,每一个等价类最早出现的位置
于是扫一遍,取一个$\max$就可以了

然后再看看这个题,也就是多连几条边的事吧?

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;
const int M = N * 12;
const LL INF = 1e17;

int n,a[N],done[N];
int nxt[M],to[M],cost[M],head[N];
LL dis[N],bmn,bmx,mn=INF;
priority_queue<pair<LL,int> > que;

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[++E] = c;
	to[E] = v; nxt[E] = head[u]; head[u] = E;
}

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Dijkstra() {
	for (int i=0;i<mn;i++) dis[i] = INF;
	dis[0] = 0; que.push(make_pair(0, 0));
	while (!que.empty()) {
		int w = que.top().second; que.pop();
		if (done[w]) continue; else done[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}

inline LL cal(LL lim) {
	LL ret = 0, tmp;
	for (int i=0;i<mn;i++) {
		if (lim < dis[i]) continue;
		ret += (lim - dis[i]) / mn + 1;
	}
	return ret;
}

int main() {
	n = read(); cin>>bmn>>bmx;
	for (int i=1;i<=n;i++) {
		a[i] = read();
		if (a[i]) mn = min(mn, (LL)a[i]);
	}
	for (int i=1;i<=n;i++) {
		if (a[i] == mn) continue;
		for (int j=0;j<mn;j++) {
			AddEdge(j, (j+a[i])%mn, a[i]);
		}
	}
	Dijkstra();
	printf("%lld\n",cal(bmx)-cal(bmn-1));
	return 0;
}

【BZOJ 3919】[Baltic2014] portals

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3919
神犇题解:http://www.cnblogs.com/clrs97/p/4668647.html

解题报告

我们自己想一想,这货如果没有Po那就是一个BFS
现在考虑Po的作用,那一定是发射一个Po之后,正常移动是为了走到最近的墙来使用Po
于是我们先预处理出每一个点上下左右每一个方向遇到的第一堵墙
再求出这到这四个点的最近距离$l$

那么如果我们当前在$i$号点,那么我们可以花费$1$的代价走到相邻的四个点
也可以花$l+1$的代价走到上下左右第一个遇到障碍的点
这显然是一个最短路问题,跑一个Dijksta就可以啦!

【BZOJ 4356】[CEOI2014] Wall

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4356
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5196611.html
神犇题解Ⅱ:http://www.cnblogs.com/New-Godess/p/4424149.html

解题报告

bzoj_4356_solution

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int L = 400 + 9;
const int N = L * L * 4;
const int M = N * 4;
const LL INF = 1e17;

int n,m,tot,E,head[N],nxt[M],to[M],cost[M];
int cx[L][L],cy[L][L],intree[L][L];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
bool del[L][L][4],vis[L][L],done[N],bst[L][L][4];
LL dis[N];
priority_queue<pair<LL, int> > que;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int c) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}

inline int id(int x, int y, int t = 0) {
	if (!t) return x + (y - 1) * (n + 1);
	else return (x - 1 + (y - 1) * (n + 1) << 2) + t;
}

inline void Dijkstra(int s) {
	memset(done, 0, sizeof(done));
	fill(dis, dis+N, INF); dis[s] = 0;
	que.push(make_pair(0, s));
	for (int w;!que.empty();) {
		w = que.top().second; que.pop(); 
		if (done[w]) continue;
		done[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	} 
}

bool mark(int x, int y, int f) {
	if (intree[x][y]) return ~intree[x][y]?1:0;
	bool tag = vis[x][y]; 
	for (int w=id(x,y),i=head[w];i;i=nxt[i]) {
		if (dis[w] + cost[i] == dis[to[i]] && to[i] != f) {
			for (int j=1,nx,ny;j<=4;j++) {
				nx = x + dx[j]; ny = y + dy[j];
				if (id(nx, ny) == to[i]) {
					if (mark(nx, ny, w)) {
						bst[x][y][j] = tag = 1;
						bst[nx][ny][j+2>4?j-2:j+2] = 1;
					}
					break;
				}
			}
		}
	}
	intree[x][y] = tag?1:-1;
	return tag;
}

int main() {
	m = read(); n = read();
	del[1][1][2] = del[1][1][4] = 1;
	for (int j=1;j<=m;j++) {
		for (int i=1;i<=n;i++) {
			if (read()) {
				vis[i][j] = 1;
				del[i][j][4] = 1;
				del[i+1][j][3] = 1;
				del[i][j+1][1] = 1;
				del[i+1][j+1][2] = 1;
			}
		}
	}
	for (int j=1,tmp;j<=m;j++) {
		for (int i=1;i<=n+1;i++) {
			cy[i][j] = tmp = read();
			Add_Edge(id(i, j), id(i, j+1), tmp);
		}
	}
	for (int j=1,tmp;j<=m+1;j++) {
		for (int i=1;i<=n;i++) {
			cx[i][j] = tmp = read();
			Add_Edge(id(i, j), id(i+1, j), tmp);
		}
	}
	Dijkstra(id(1,1));  
	mark(1, 1, id(1, 1));  
	E = 0; memset(head,0,sizeof(head));
	for (int j=1;j<=m+1;j++) {
		for (int i=1;i<=n+1;i++) {
			if (!del[i][j][1]) {
				if (!del[i][j][4] && !bst[i][j][1]) Add_Edge(id(i, j, 1), id(i, j, 4), 0);
				if (i <= n && !del[i+1][j][2]) Add_Edge(id(i, j, 1), id(i+1, j, 2), cx[i][j]);
			}
			if (!del[i][j][2]) {
				if (!del[i][j][1] && !bst[i][j][4]) Add_Edge(id(i, j, 2), id(i, j, 1), 0);
				if (!del[i][j][3] && !bst[i][j][3]) Add_Edge(id(i, j, 2), id(i, j, 3), 0);
			}
			if (!del[i][j][3]) {
				if (!del[i][j][4] && !bst[i][j][2]) Add_Edge(id(i, j, 3), id(i, j, 4), 0);
				if (j <= m && !del[i][j+1][2]) Add_Edge(id(i, j, 3), id(i, j+1, 2), cy[i][j]);
			}
			if (!del[i][j][4]) {
				if (i <= n && !del[i+1][j][3]) Add_Edge(id(i, j, 4), id(i+1, j, 3), cx[i][j]);
				if (j <= m && !del[i][j+1][1]) Add_Edge(id(i, j, 4), id(i, j+1, 1), cy[i][j]);
			}
		}
	}
	Dijkstra(id(1,1,3));
	printf("%lld\n",dis[id(1,1,1)]);
	return 0;
}

【BZOJ 4144】[AMPPZ2014] Petrol

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4144
神犇题解:http://www.cnblogs.com/Tunix/p/4593049.html

解题报告

随便想一想,这题似乎除了有加油站的点之外,其他点似乎完全可以不用考虑?
再仔细想一想的话,我们似乎只要求出任意两个有加油站的点的最短路,然后再做一个MST就可以了!

现在的问题就是如何求出任意两点的最短路了
我们考虑放宽一点条件,求出一些最短路径的集合 $\{ e \}$ ,使其能够凑出任意两点的最短路
现在考虑两点之间最短路的性质:

定义$blg(x)$表示离$x$最近的关键点
那么对于 $a \to b$ 最短路上,一定是前一部分$blg(x)=a$,后一部分$blg(x)=b$
于是我们就可以通过枚举原图中的一条边$(x_1,x_2)$并且判断$blg(x_1)$是否等于$blg(x_2)$来找到所有中途不经过加油站的最短路

如何证明呢?考虑反证法:如果中途有一个点$blg(y)=c$那么先从$a \to b \to c$一定不比$a \to b$劣
这是因为如果我们走到y点后绕道到c点去加油,回来的时候油量一定不少于从a点到y点的油量

这样我们就可以找到一个边集 $\{ \varepsilon \}$使得 $\{ e\} \subset \{ \varepsilon \}$
于是我们把$\{ \varepsilon \}$拿出来,做一个最小生成树,然后查询的时候,在树上倍增一下就可以啦!

【BZOJ 4456】[ZJOI2016] 旅行者

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4456
神犇题解:http://blog.csdn.net/neither_nor/article/details/51733997

解题报告

将询问离线后考虑分治
不停地将区间尽量划分成正方形
考虑每一个块内的询问:

1. 最优路径经过中轴线

那么我们枚举中轴线上的每一个点
跑一遍到块内所有点的最短路
然后用这个东西来更新答案

2. 最优路径不经过中轴线

那么我们递归处理

于是我们就在 $O(n\sqrt n {\log ^2}n)$ 的时间复杂度内解决这个问题了
然而复杂度可以被证明到少个 $log$ 参见:http://blog.csdn.net/neither_nor/article/details/51733997

【BZOJ 4152】[AMPPZ2014] The Captain

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4152
神犇题解:http://blog.csdn.net/qq_34731703/article/details/52724766

解题报告

因为横着的边和竖着的边相互独立
于是分开考虑,先考虑横着的边:

直接连是 $ O({n^2})$
但因为 $ dis(i,j) = dis(i,k) + dis(k,j)(i < k < j)$ 所以只连相邻的点就可以啦!

竖着的边也同理
这样的话,边数和点数都是 $ O(n)$ 级别的
于是就可以上正常的最短路辣!
另外,据说这题卡SPFA?

【BZOJ 4383】[POI2015] Pustynia

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4383
数据传送门:http://oi.cyo.ng/?attachment_id=1911

题解

这个题暴力差分肯定可以做,就是边太多会爆炸
于是我们考虑先建一个像线段树一样的图
于是原题可以拆成6e5个区间连边
每一个区间又可以拆成log(n)个线段树上的点
于是复杂度就对辣!

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000000;
const int M = 5000000;
const int INF = 1000000000;

int head[N],to[M],nxt[M],cost[M],val[N],arr[N];
int sol[N],vis[N],in[N],n,m,s,bas,tot;
queue<pair<int,int> > leaf;

inline void Add_Edge(int u, int v, int w) {
	static int T = 0; in[v]++;
	to[++T] = v; nxt[T] = head[u]; 
	head[u] = T; cost[T] = w;
}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

void build(int w, int l, int r) {
	bas = max(bas, w);
	if (l < r) {
		int mid = l + r + 1 >> 1;
		Add_Edge(w, w<<1, 0); build(w<<1, l, mid - 1);
		Add_Edge(w, w*2+1, 0); build(w*2+1, mid, r);
	} else {
		leaf.push(make_pair(w,l));
	}
}

bool Get_Ans(int w) {
	sol[w] = true;
	for (int i=head[w];i;i=nxt[i]) {
		if (vis[to[i]] && val[w] - cost[i] < val[to[i]]) {
			return false;
		} else {
			val[to[i]] = min(val[to[i]], val[w] - cost[i]);
			if (--in[to[i]] == 0) {
				if (!Get_Ans(to[i])) {
					return false;
				};
			}
		}
	}
	return true;
}

inline bool solve() {
	for (int i=1;i<=tot;i++) {
		if (!sol[i] && !in[i]) {
			if (!Get_Ans(i)) {
				return false;
			}
		}
	}
	return true;
} 

void insert(int w, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		Add_Edge(tot, w, 0);
	} else {
		int mid = l + r + 1 >> 1;
		if (L < mid) insert(w<<1, l, mid-1, L, R);
		if (R >= mid) insert(w*2+1, mid, r, L, R);
	}
}

int main(){
	n = read(); s = read(); m = read();
	build(1,1,n);
	while (!leaf.empty()) { 
		Add_Edge(leaf.front().first, leaf.front().second + bas, 0);
		leaf.pop(); 
	}
	tot = bas + n;
	fill(val, val+N, INF);
	for (int i=1,p;i<=s;i++) {
		p = read();
		val[p+bas] = read();
		vis[p+bas] = 1;
	}
		
	for (int i=1,l,r,k,last;i<=m;i++) {
		l = read(); r = read(); 
		k = read(); ++tot;
		for (int j=1,tmp;j<=k;j++) {
			arr[j] = tmp = read();
			Add_Edge(bas+tmp, tot, 1);
		}
		arr[0] = l-1; arr[k+1] = r+1;
		for (int j=1;j<=k+1;j++) {
			if (arr[j] - arr[j-1] > 1) {
				insert(1,1,n,arr[j-1]+1,arr[j]-1);
			} 
		}
	}
	if (!solve()) {
		puts("NIE");
	} else {
		for (int i=bas;i<=tot;i++) {
			if (in[i] || val[i] < 1) {
				puts("NIE");
				exit(0);
			}
		}
		
		puts("TAK");
		for (int i=1;i<=n;i++) 
			printf("%d ",val[i+bas]);
	}
	return 0;
}

【Codevs 1817】灾后重建

题目传送门:http://codevs.cn/problem/1817/

这题可以说是Floyd的最终考验吧?
具体来说:做了这题Floyd的原理就完全明白了吧!
详细请参考《算导》P405吧!(难得算导说了一次人话)

#include<iostream>
#include<cstdio>
#include<vector>
#define INF 1000099 
using namespace std;

struct abc{int point,len;};
int n,m;
int t[299]={0};
int f[299][299];
bool yet[299]={0};
vector<abc> path[299];  
bool day[100099]={0};
int pro=0;

void init(){
	for (int i=1;i<=250;i++){
		t[i]=INF;
	}
	for (int i=0;i<=250;i++){
	    for (int j=0;j<=250;j++){
		    f[i][j]=INF;
	    }
	}
    scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
	    scanf("%d",&t[i]); 
	    if (t[i]==0) yet[i]=true;
	}	
	abc hc;
	for (int i=1,a,b,leng;i<=m;i++){
		scanf("%d%d%d",&a,&b,&leng);
		a++;b++;
		f[a][b]=leng;f[b][a]=leng;
		hc.point=b;hc.len=leng;
		path[a].push_back(hc);
		hc.point=a;
		path[b].push_back(hc);
	}
}

void update(int num){
	int end,length;
	for (int k=pro+1;k<=end;k++)
	    yet[k]=true;
	for (int k=pro+1;k<=end;k++){
	    for (int i=1;i<=n;i++){
	    	for (int j=1;j<=n;j++){
	    		f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	    	}
	    }
	}
	pro=end; 
} 

int main(){
	int Q,x,y,ti;
	init();
	cin>>Q;
	for (int i=1;i<=Q;i++){
		scanf("%d%d%d",&x,&y,&ti);
		x++;y++;
		if (!day[ti]) {
		    update(ti);
			day[ti]=1;
		}
		if (f[x][y]<INF && yet[x] && yet[y]) printf("%d\n",f[x][y]);
		else printf("-1\n");
	}
	return 0;
}

为什么去年写的代码这么丑? (╯‵□′)╯︵┻━┻

【UVa 1027】Toll

题目传送门:https://uva.onlinejudge.org/index.php?problem=3468
中文题面:《算法竞赛·入门经典·训练指南》P331

一直以为是一个建图非常神奇的最短路/网络流
然而居然是类似斯坦纳树一样的转移怪异的DP
qrrxcieey4qta4clrvl

设d[i]为满足题目条件的情况下,到达第i个点时的最少货物量
然后反向各更新即可

更新的方式的话,显然SPFA的正确性没有问题
又因为没有负权,所以Dijkstra也是正确的?

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 70;
const int M = 2000+9;
const double EPS = 1e-4;

int head[N],nxt[M],to[M],m,T,MN,s,t,case_cnt;
LL d[N]; bool inq[N]; queue<int> que; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int ID(const char c) {
	if ('a' <= c && c <= 'z') return c - 'a' + 1;
	else return c - 'A' + 27;
}

inline void Add_Edge(int u, int v) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

inline LL cost(int w, LL val) {
	if (w == s) return 0;
	else if (w <= 26) return 1;
	else {
		LL l=1,r=1e15,ret=1,mid;
		while (l <= r) {
			mid = l + r >> 1;
			if (val+mid-(LL)(ceil((val+mid)/20.0)+EPS) >= val) ret = mid, r = mid - 1;
			else l = mid+1;
		}
		return ret;
	}
}	

inline LL SPFA() {
	memset(d,0x3f,sizeof(d));
	d[t] = MN + (s!=t?cost(t, MN):0); 
	inq[t] = 1; que.push(t);
	
	while (!que.empty()) {
		int w = que.front(); inq[w] = 0; que.pop();
		for (int i=head[w];i;i=nxt[i]) {
			if (d[to[i]] > d[w] + cost(to[i],d[w])) {
				d[to[i]] = d[w] + cost(to[i],d[w]);
				if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
			}
		}
	}
	return d[s];
}

int main(){
	static char U[10],V[10];
	for (m=read();~m;m=read(),T=0) {
		memset(head,0,sizeof(head));
		
		for (int i=1;i<=m;i++) {
			scanf("%s %s",U+1,V+1);
			Add_Edge(ID(U[1]), ID(V[1]));
		}
		
		MN = read();
		scanf("%s %s",U+1,V+1);
		s = ID(U[1]); t = ID(V[1]);
		printf("Case %d: %lld\n",++case_cnt,SPFA());
	}
	return 0;
}

【UVa 1416】Warfare And Logistics

题目传送门:https://uva.onlinejudge.org/index.php&problem=4162
中文题面:《算法竞赛·入门经典·训练指南》P330

首先,这题看数据范围就是一个大暴力
然而我只会O(m*n^3)的、会T到死的、辣鸡到爆炸的大暴力
f0754h_js27jw9sby3i

枚举每一个最短路的起点,考虑只有删除最短路树上的边才会影响到答案
于是就只用枚举O(n^2),最终复杂度为O(n^2mlog(n))

【BZOJ 2069】[POI2004] ZAW

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2069
数据传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/2069.rar

这题说两个做法:
1)最短路+奇怪的姿势,时间复杂度O(nlogn)
2)关键点间的最短路,时间复杂度O(nlog^2n)

先说第一种方式:
从1开始跑最短路,每个点记录最短路+次短路,保证路径上第二个点不同(1算第一个点)
然后O(n)扫描每一个点,使用最短路+次短路更新答案即可
这种方法虽然时间复杂度较优,但不是很通用

接下来我们说一说关键点间的最短路:
考虑将答案路径与1相连的两条边删掉
路径变为与1相连的点间的最短路径
于是将与1相邻的点设为关键点,跑关键点间的最短路即可

接下来说一说怎么跑关键点间的最短路:
考虑拆二进制,枚举二进制的每一位。
根据这一位是否为1,将关键点分为两个点集
然后一个连超级源,另一个连超级汇即可
时间复杂度O(nlog^2(n))
其实这才是这篇题解的重点

这里是二进制拆分+Dijkatra的代码,请随意食用~

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 50000+9;
const int M = 300000+9;
const int INF = 1e9;

int head[N],dis[N],t1[N],t2[N],t3[N],head_tmp[N],tot,TT,S,T,vout=INF,n,m,nxt[M],to[M],cost[M];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que; bool vis[N]; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v, int c1, int c2) {
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = c1;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = c2;
}

inline int Dijkstra() {
	memset(dis,60,sizeof(dis));
	memset(vis,0,sizeof(vis));
	que.push(make_pair(0,S));
	dis[S] = 0; vis[1] = 1;
	
	while (!que.empty()) {
		int w = que.top().second; que.pop();
		if (vis[w]) continue;
		else vis[w] = 1; 
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i] && !vis[to[i]]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(dis[to[i]], to[i]));	
			} 
		}
	}
	return dis[T];
}

int main(){
	n = read(); m = read();
	for (int i=1,a,b,c,d;i<=m;i++) {
		a = read(); b = read();
		c = read(); d = read();
		Add_Edge(a, b, c, d);
		
		if (a == 1) {
			t1[++tot] = b;
			t2[tot] = c;	
			t3[tot] = d;
		} else if (b == 1) {
			t1[++tot] = a;
			t2[tot] = d;
			t3[tot] = c;
		}
	}
	
	S = N - 1; T = N - 2;
	int w = 0, TMP = n, ori = TT;
	while (TMP) w++, TMP >>= 1;
	memcpy(head_tmp,head,sizeof(head));
	
	for (int k=0,cur=1;k<=w;k++,cur<<=1) {
		TT = ori;
		memcpy(head,head_tmp,sizeof(head));
		
		for (int i=1;i<=tot;i++) {
			if (t1[i]&cur) Add_Edge(S,t1[i],t2[i],INF);
			else Add_Edge(t1[i],T,t3[i],INF);
		} 
		vout = min(Dijkstra(), vout);
		
		TT = ori;
		memcpy(head,head_tmp,sizeof(head));
		
		for (int i=1;i<=tot;i++) {
			if (t1[i]&cur) Add_Edge(t1[i],T,t3[i],INF);
			else Add_Edge(S,t1[i],t2[i],INF);
		} 
		vout = min(Dijkstra(), vout);
	}
	printf("%d\n",vout);
	return 0;
}

【NOIP十连测】[D1T3] Walk

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/noip_test1_statements.pdf

唯一恶心的就是哪些根据val建的边
于是搞一个想分层图一样的玩意儿
然后有的边权为零,于是BFS的时候不往队首扔,往队尾扔即可

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1300000;
const int M = 200000*2+300000+9;

int n,m,head[N],nxt[M],to[M],dis[N];
deque<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline void BFS() {
	memset(dis,-1,sizeof(dis));
	dis[1] = 0; que.push_back(1);
	
	while (!que.empty()) {
		int w = que.front(); que.pop_front();
		for (int i=head[w];i;i=nxt[i]) 
			if (w <= n) {
				if (!~dis[to[i]] || dis[to[i]] > dis[w] + 1) dis[to[i]] = dis[w] + 1, que.push_back(to[i]);
			} else {
				if (!~dis[to[i]] || dis[to[i]] > dis[w]) dis[to[i]] = dis[w], que.push_front(to[i]);
			}
		if (w > n) for (int i=0;i<=20;i++) if ((w-n)&(1<<i)) {
			int v = ((w-n)^(1<<i)) + n; if (v <= n) continue;
			if (!~dis[v] || dis[v] > dis[w]) dis[v] = dis[w], que.push_front(v);
		} 
	}
}

int main(){
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	n = read(); m = read();
	for (int i=1,tmp;i<=n;i++) tmp = read(), Add_Edge(i,n+tmp), Add_Edge(n+tmp,i);
	for (int i=1,u,v;i<=m;i++) u = read(), v = read(), Add_Edge(u,v);
	BFS(); for (int i=1;i<=n;i++) printf("%d\n",dis[i]);
	return 0;
}

【Codeforces 715B】Complete The Graph

题目传送门:http://codeforces.com/contest/716/problem/D
官方题解:http://codeforces.com/blog/entry/47169

这题很好玩,有两种写法。

1)暴力最短路,复杂度O(nmlogn)
做法就是每一次找最短路,然后改一改

2)神奇二分,复杂度O(mlognlogm)
将可更改的边拉出来,排成一溜
二分一个点k,使1~k的边为1,其余边为INF
终止条件:k时最短路<=l,k-1时最短路>L
于是第k条边就是关键边,只用考虑这条边的长度即可
感觉好神!

考试的时候,我写的是第一种

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const LL N = 1000+9;
const LL M = 20000+9;
const LL INF = 1e14;

LL head[N],to[M],nxt[M],cost[M],U[M],V[M],dis[N],n,m,L,S,T,sign[M],ty,inq[N],sur[N];
queue<LL> que;

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(LL u, LL v, LL d) {
	static LL TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = d;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = d;
}

inline LL SPFA(){
	for (int i=1;i<=n;i++) dis[i] = INF;
	dis[S] = 0; que.push(S), inq[S] = 1;
	
	while (!que.empty()) {
		LL w = que.front(); que.pop(); inq[w] = 0;
		for (LL i=head[w];i;i=nxt[i]) if (~cost[i] && dis[to[i]] > dis[w]+cost[i]) {
			dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
			if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
		}
	} return dis[T];
}

int main(){
	n = read(); m = read(); L = read(); S = read() + 1; T = read() + 1;
	for (LL i=1,tmp;i<=m;i++) {
		U[i] = read()+1, V[i] = read()+1; tmp = read();
		if (!tmp) tmp = -1, sign[i] = 1;
		Add_Edge(U[i],V[i],tmp);
	}
	if (SPFA() < L) cout<<"NO", exit(0);
	for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = 1;
	if ((ty=SPFA()) > L) cout<<"NO", exit(0);
	for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = INF;
	LL w = T,len_tmp; while (w != S) {if(sign[sur[w]/2]) cost[sur[w]] = cost[sur[w]^1] = 1; w = to[sur[w]^1];}
	while ((len_tmp=SPFA()) < L) 
		for (w=T;w!=S;w=to[sur[w]^1]) if (sign[sur[w]/2]) {
			cost[sur[w]] += L - len_tmp, cost[sur[w]^1] += L - len_tmp; break;}
	cout<<"YES"<<endl;
	for (LL i=1;i<=m;i++) 
		if (sign[i] && cost[i*2] == -1) printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,L+1);
		else printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,cost[i*2]);
	return 0;
}