最短路训练

SPFA+二分

[USACO08JAN] Telephone Lines S

题目描述

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.

There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John's property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.

The i-th cable can connect the two distinct poles Ai and Bi, with length Li (1 ≤ Li ≤ 1,000,000) units if used. The input data set never names any {Ai, Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.

As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.

Determine the minimum amount that Farmer John must pay.

多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着 \(1\le N\le1000\) 根据 \(1\cdots N\) 顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有 \(1\le p\le10000\) 对电话杆可以拉电话线。其他的由于地震使得无法连接。

第i对电线杆的两个端点分别是 \(a_i\) ，\(b_i\)，它们的距离为 \(1\le l_i\le1000000\)。数据中每对 \((a_i,b_i)\) 只出现一次。编号为 \(1\) 的电话杆已经接入了全国的电话网络，整个市的电话线全都连到了编号 \(N\) 的电话线杆上。也就是说，笨笨的任务仅仅是找一条将 \(1\) 号和 \(N\) 号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。

电信公司决定支援灾区免费为此市连接 \(k\) 对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度（每根电话线仅连接一对电话线杆）。如果需要连接的电话线杆不超过 \(k\) 对，那么支出为 \(0\)。

请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？

输入格式

输入文件的第一行包含三个数字 \(n,p,k\)。

第二行到第 \(p+1\) 行，每行分别都为三个整数 \(a_i,b_i,l_i\)。

输出格式

一个整数，表示该项工程的最小支出，如果不可能完成则输出 -1。

样例 #1

样例输入 #1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

样例输出 #1

4

采用二分+SPFA的思路进行解决

二分最大的长度

如果小于这个长度就直接不需要花钱，相当于路径为0

不然就是大于这个长度，路径直接加一。

然后直接判断即可。

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
#define ll long long
#define int long long
const int N=1e3+100;
const int M=1e4+10;
struct edge
{
    int to,nex,w;
}e[M<<1];
int cnt;
int head[N];
int n,p,k;
int dis[N];
bool vis[N];
void add(int x,int y,int z)
{
    e[++cnt].nex=head[x];
    head[x]=cnt;
    e[cnt].w=z;
    e[cnt].to=y;
}
//链式前向星存图
bool check(int mid)
{
queue<int>q;
memset(dis,0x3f,sizeof dis);
dis[1]=0;
vis[1]=1;
q.push(1);
while(!q.empty())
{
    int s;
    int k=q.front();
    q.pop();
    for(int i=head[k];i;i=e[i].nex)
    {
        int v=e[i].to;
        if(e[i].w>mid)
        {
            s=dis[k]+1;
        }
        else
        {
            s=dis[k];
        }
        if(s<dis[v])
        {
            dis[v]=s;
            if(!vis[v])
            {
                vis[v]=1;
                q.push(v);
            }
        }
    }
    vis[k]=0;
}
if(dis[n]<=k)
{
    return 1;
}
    //二分
return 0;
}
signed main()
{
    cin>>n>>p>>k;
    rep(i,1,p)
    {
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
    }   
    int l=0;
    int r=1e6;
    int mid;
    int ans=-1;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

SPFA+双端队列（水过）

[USACO11JAN] Roads and Planes G

题面翻译

题面描述

Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 \(T\) 个城镇 ( \(1 \le T \le 25,000\) )，编号为 \(1\) 到 \(T\) 。这些城镇之间通过 \(R\) 条道路 ( \(1 \le R \le 50,000\) ，编号为 \(1\) 到 \(R\) ) 和 \(P\) 条航线 ( \(1 \le P \le 50,000\) ，编号为 \(1\) 到 \(P\) ) 连接。每条道路 \(i\) 或者航线 \(i\) 连接城镇 \(A_i\) ( \(1 \le A_i \le T\) )到 \(B_i\) ( \(1 \le B_i \le T\) )，花费为 \(C_i\) 。

对于道路 \(0 \le C_i \le 10,000\) ;然而航线的花费很神奇，花费 \(C_i\) 可能是负数( \(-10,000 \le C_i \le 10,000\) )。道路是双向的，可以从 \(A_i\) 到 \(B_i\)，也可以从 \(B_i\) 到 \(A_i\) ，花费都是 \(C_i\) 。然而航线与之不同，只可以从 \(A_i\) 到 \(B_i\) 。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台 了一些政策保证：如果有一条航线可以从 \(A_i\) 到 \(B_i\)，那么保证不可能通过一些道路和航线从 \(B_i\) 回到 \(A_i\) 。由于 \(FJ\) 的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 \(S\) ( \(1 \le S \le T\)) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

输入格式

共 \(R+P+1\) 行

第 \(1\) 行：四个整数 \(T\) , \(R\) , \(P\) 和 \(S\) ，分别表示城镇的数量，道路的数量，航线的数量和中心城镇。

第 \(2\) 到 \(R+1\) 行：每行三个整数 \(A_i\) , \(B_i\) 和 \(C_i\) ，描述一条道路。

第 \(R+2\) 到 \(R+P+1\) 行：每行三个整数 \(A_i\) , \(B_i\) 和 \(C_i\) ，描述一条航线。

输出格式

共 \(T\) 行，第 \(i\) 行输出城市 \(S\) 到城市 \(i\) 的最小花费。如果不能到达，输出NO PATH

题目描述

Farmer John is conducting research for a new milk contract in a new territory. He intends to distribute milk to T (1 <= T <= 25,000) towns conveniently numbered 1..T which are connected by up to R (1 <= R <= 50,000) roads conveniently numbered 1..R and/or P (1 <= P <= 50,000) airplane flights conveniently numbered 1..P.

Either road i or plane i connects town A_i (1 <= A_i <= T) to town B_i (1 <= B_i <= T) with traversal cost C_i. For roads, 0 <= C_i <= 10,000; however, due to the strange finances of the airlines, the cost for planes can be quite negative (-10,000 <= C_i <= 10,000).

Roads are bidirectional and can be traversed from A_i to B_i or B_i to A_i for the same cost; the cost of a road must be non-negative.

Planes, however, can only be used in the direction from A_i to B_i specified in the input. In fact, if there is a plane from A_i to B_i it is guaranteed that there is no way to return from B_i to A_i with any sequence of roads and planes due to recent antiterror regulation.

Farmer John is known around the world as the source of the world's finest dairy cows. He has in fact received orders for his cows from every single town. He therefore wants to find the cheapest price for delivery to each town from his distribution center in town S (1 <= S <= T) or to know that it is not possible if this is the case.

MEMORY LIMIT: 64MB

输入格式

* Line 1: Four space separated integers: T, R, P, and S

* Lines 2..R+1: Three space separated integers describing a road: A_i, B_i and C_i

* Lines R+2..R+P+1: Three space separated integers describing a plane: A_i, B_i and C_i

输出格式

* Lines 1..T: The minimum cost to get from town S to town i, or 'NO PATH' if this is not possible

样例 #1

样例输入 #1

6 3 3 4 
1 2 5 
3 4 5 
5 6 10 
3 5 -100 
4 6 -100 
1 3 -10

样例输出 #1

NO PATH 
NO PATH 
5 
0 
-95 
-100

提示

6 towns. There are roads between town 1 and town 2, town 3 and town 4, and town 5 and town 6 with costs 5, 5 and 10; there are planes from town 3 to town 5, from town 4 to town 6, and from town 1 to town 3 with costs -100, - 100 and -10. FJ is based in town 4.

FJ's cows begin at town 4, and can get to town 3 on the road. They can get to towns 5 and 6 using planes from towns 3 and 4. However, there is no way to get to towns 1 and 2, since they cannot go

backwards on the plane from 1 to 3.

首先是队列不同：

在普通的SPFA内，我们一般会定义这样的队列

queue< int >q;

但是呢，SLF优化需要这个

deque< int >q;

deque相比于queue可以支持双端的插入和退出操作，分别为

q.push_front(a);
q.push_back(a);
q.pop_front();
q.pop_back();

第二是SLF优化思想

普通的SPFA是只会在队头插入值，而SLF优化会在插入前与队头元素进行比较。

如果当前点比队头元素的dis值小，则将其插入到队头，否则将其插入到队尾。

原因是优先拓展更优的点可以减少拓展不优的点，从而减少总的入队次数，使SPFA更快地收束。

核心代码如下

if(!q.empty()&&dist[v]>=dist[q.front()]) q.push_back(v);
else q.push_front(v);

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define MAXM 1000100
#define MAXN 100010
#define ri register int
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
struct node
{
	int from,to,dis;
} edge[MAXM];
int head[MAXM],cnt,n,r,p,s,dist[MAXN];
bool vis[MAXN];
inline void add(int from,int to,int dis)
{
	edge[++cnt].from=head[from];
	edge[cnt].to=to;
	edge[cnt].dis=dis;
	head[from]=cnt;
}
inline void SPFA(int s)
{
	deque< int >q;
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	q.push_back(s);
	vis[s]=1;
	while(!q.empty())
	{
		int now=q.front();
		q.pop_front();
		for(int i=head[now]; i; i=edge[i].from)
		{
			int v=edge[i].to;
			if(dist[v]>dist[now]+edge[i].dis)
			{
				dist[v]=dist[now]+edge[i].dis;
				if(!vis[v])
				{
					if(!q.empty()&&dist[v]>=dist[q.front()]) 
                    q.push_back(v);
					else q.push_front(v);
					vis[v]=1;
				}
			}
		}
		vis[now]=0;
	}
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>r>>p>>s;
	int u,v,w;
	rep(i,1,r)
	{
        cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
    //双向边
    rep(i,1,p)
	{
        cin>>u>>v>>w;
		add(u,v,w);
	}
	SPFA(s);
	rep(i,1,n)
	{
		if(dist[i]>=1061109567) 
         //注意这里不能直接写dist[i]==0x3f 
		{
			cout<<"NO PATH"<<'\n';

		}
		else
		{
			cout<<dist[i]<<'\n';
		}
	}
	return 0;
}

拓补排序解题

Description

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy...y. Sorted sequence cannot be determined. Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

Sample Input

4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0

Sample Output

Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.

上个模板

vector<int> edge[500];
int in[30];
int m;
vector<int> ans;
int topo() {
    ans.clear();
    queue<int> q;
    for (int i = 0; i < m; i++) {
        if (in[i] == 0)
            q.push(i);
    }
    bool flag = false;
    while (!q.empty()) {
        if (q.size() > 1)
            flag = true;
        int p = q.front();
        q.pop();
        ans.push_back(p);
        for (int i = 0; i < edge[p].size(); i++) {
            int y = edge[p][i];
            in[y]--;
            if (in[y] == 0)
                q.push(y);
        }
    }
    if (ans.size() < m) {
        return -1;
    } else if (flag)
        return 0;
    else
        return 1;
}

然后来解决此题

1. 当入度为0的顶点个数为0,说明有环,拓扑排序后,拓扑序列中点的个数小于n也说明有环,这种情况就是无序.
2. 如果在拓扑排序的过程中,如果入度为0的顶点个数 > 1,则无法确定. 这种情况的结果就是无法确定.
3. 除了以上两种,就是拓扑有序的,最后输出拓扑序列即可.

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define mp make_pair
#define met(a, x) memset(a,x,sizeof(a))

using namespace std;
const int mod = 1e9 + 7;
const int N = 50005;
vector<int> edge[500];
int in[30], tmp[30];
int m, n;
vector<int> ans;

int topo() {
    ans.clear();
    queue<int> q;
    for (int i = 0; i < m; i++) {
        if (in[i] == 0)
            q.push(i);
    }
    bool flag = false;
    while (!q.empty()) {
        if (q.size() > 1)
            flag = true;
        int p = q.front();
        q.pop();
        ans.push_back(p);
        for (int i = 0; i < edge[p].size(); i++) {
            int y = edge[p][i];
            in[y]--;
            if (in[y] == 0)
                q.push(y);
        }
    }
    if (ans.size() < m) {
        return -1;
    } else if (flag)
        return 0;
    else
        return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    char str[5];
    while (cin >> m >> n && m && n) {
        for (int i = 0; i < 500; i++)
            edge[i].clear();
        met(in, 0);
        met(tmp, 0);
        int flag = 0;
        int num = 0;
        for (int i = 1; i <= n; i++) {
            cin >> str;
            if (flag != 0)
                continue;
            int a = str[0] - 'A';
            int b = str[2] - 'A';
            if (str[1] == '<') {
                in[b]++;
                edge[a].push_back(b);
            } else {
                in[a]++;
                edge[b].push_back(a);
            }
            memcpy(tmp, in, sizeof(in));
            flag = topo();
            memcpy(in, tmp, sizeof(tmp));
            if (flag != 0) 
            {
                num = i;
            }
            //这里就是已经出现了结果了
        }
        char c;
        if (flag == 1) {
            cout << "Sorted sequence determined after " << num << " relations: ";
            for (int i = 0; i < ans.size(); i++) {
                c = (ans[i] + 'A');
                cout << c;
            }
            cout <<'.'<< endl;
        } else if (flag == 0) {
            cout << "Sorted sequence cannot be determined." << endl;
        } else {
            cout << "Inconsistency found after " << num << " relations." << endl;
        }
    }
    return 0;
}

矩阵乘法 + 最短路 + DP

[USACO07NOV] Cow Relays G

题面翻译

给定一张 \(T\) 条边的无向连通图，求从 \(S\) 到 \(E\) 经过 \(N\) 条边的最短路长度。

输入格式

第一行四个正整数 \(N,T,S,E\) ，意义如题面所示。

接下来 \(T\) 行每行三个正整数 \(w,u,v\) ，分别表示路径的长度，起点和终点。

输出格式

一行一个整数表示图中从 \(S\) 到 \(E\) 经过 \(N\) 条边的最短路长度。

数据范围

对于所有的数据，保证 \(1\le N\le 10^6\)，\(2\le T\le 100\)。

所有的边保证 \(1\le u,v\le 1000\)，\(1\le w\le 1000\)。

题目描述

For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.

Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.

To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.

Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.

给出一张无向连通图，求S到E经过k条边的最短路。

输入格式

* Line 1: Four space-separated integers: N, T, S, and E

* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i

输出格式

* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.

样例 #1

样例输入 #1

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

样例输出 #1

10

首先，我们有两个矩阵，如果其中一个矩阵代表恰好经过x条边的最短路，另外一个矩阵代表恰好经过y条边的最短路。那么将这两个矩阵合并就代表恰好经过x+y条边的最短路。怎么合并呢？结合下面这个式子理解一下：

c[i][j]=min(c[i][j],a[i][k]+b[k][j]);

其中i,j,k就是floyd三层循环里的i,j,k ;而a矩阵是经过x条边的最短路，b矩阵是经过y条边的最短路，那么c矩阵就是我们得到的经过x+y条边的最短路了。

那么我们依据初始输入的数组（也就是只经一条边两个点的距离）,这样转移n-1次，就可以得出我们想要的答案了；

然而这样显然会炸啊！那怎么办呢？我们可以借助类似快速幂的操作去实现。

另外我们还可以将编号离散化

#include <bits/stdc++.h>
using namespace std;
int num[1000005];
int n,s,t,e,tol;
struct map
{
    int a[500][500];
    map operator * (const map &x) const //重载运算符，一会儿要用
    {
        map c;
        memset(c.a,0x3f3f3f3f,sizeof(c.a));//取min，显然置大数
        for(int k=1;k<=tol;k++)
            for(int i=1;i<=tol;i++)
                for(int j=1;j<=tol;j++)
                    c.a[i][j]=min(c.a[i][j],a[i][k]+x.a[k][j]);
        return c;		
    }
}dis,ans;
void init()
{
    memset(dis.a,0x3f3f3f3f,sizeof(dis.a));
    int x,y,z;
    cin>>n>>t>>s>>e;
    for(int i=1;i<=t;i++)
    {
        cin>>x>>y>>z;
        //这里做一个离散化
        if(!num[y])  
            num[y]=++tol;
        if(!num[z])
            num[z]=++tol;
        dis.a[num[y]][num[z]]=dis.a[num[z]][num[y]]=x;
    }
}
void doit() 
    //快速幂
{
    n--;
    ans=dis;
    while(n)
    {
        if(n&1)
            ans=ans*dis;
        dis=dis*dis;
        n>>=1;
    }
}
int main()
{
    init();
    doit();
    cout<<ans.a[num[s]][num[e]];
}