先写反思给自己看
- dijkstra里的dis数组,初始值为1e18才保险。这场的点数N边数M范围是1e4,边长的范围是1e9。所以初始值无穷应该取到1e18才保险。
- 多组样例,全局变量都初始化一遍吧。虽然说有些数组会在运行过程中被重写。一定要注意样例的组数,如果样例组数过多的话,memset会TLE的,得用for一个一个初始化!
题目链接 - 补充,第一条说得不全对。正无穷应该取到(边数*长度)。
题意
一个有向图,Jerry要从1点走到n点,然而tom想在这些路上拦住jerry,使得jerry从1点走到n点的最短距离变长。拦住一条边的消耗是这条边的长度,求最小的消耗。
思路
设数组dis[i] 表示1点到i点的最短距离,这点我们可以用dijkstra来求。
对于任意从u到v的长度为w的边edge(u, v, w),如果dis[v] == dis[u] + w(u, v);
说明这条边在最短路上。我们把这条边加入到新图中。
最后对新图求最小割,也就是最大流,得到的值就是jerry的最小花费。
要注意的地方
- 一定要把全局变量一个一个初始化了
- 自己造数据测一下看看对不对,图论的数据不好出但还是可以的。
- dijkstra算法里的正无穷一定要取到足够都大!
- 有一个样例是因为没开long long导致没过,我也不知道具体哪个爆了,最后把所有int换成long long了。
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const long long inf = 2e9;
const long long oo = 1e18;
#define LOCAL
const long long maxn = 3e4 + 7;
/*
建两个图,一个是正的一个是反的。
正的图用于计算从起点到某个点的最短距离
反的图用于计算终点到某个点的距离,其实也就是这个点到终点的距离
然后枚举每一条边,判断从起点到该点,该点到终点的距离,
*/
long long n, m, x, y, z;
long long d1[maxn];
long long isVisited[maxn];
struct edge
{
long long start;
long long to;
long long length;
edge(){}
edge(long long _start, long long _to, long long _length):start(_start), to(_to), length(_length){}
bool operator<(const edge & other){
return length < other.length;
}
};
struct node
{
long long id;
long long length;
node(){}
node(long long _id, long long _length){
id = _id;
length = _length;
}
bool operator<(const node & other) const{
return length > other.length;
}
};
std::vector<edge> G[maxn];
// std::vector<edge> G2[maxn];
std::vector<edge> all_edge;
long long head[maxn], ver[maxn], Edge[maxn], Next[maxn], d[maxn];
long long s, t, tot, maxflow;
queue<long long> q;
void add(long long x, long long y, long long z){
ver[++tot] = y, Edge[tot] = z, Next[tot] = head[x], head[x] = tot;
ver[++tot] = x, Edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
bool bfs(){
//cout << s << " " << t << endl;
memset(d, 0, sizeof(d));
while (q.size()) q.pop();
q.push(s); d[s] = 1;
while (q.size()){
long long x = q.front(); q.pop();
//cout << x << endl;
for (long long i = head[x]; i; i = Next[i])
if (Edge[i] && !d[ver[i]]){
q.push(ver[i]);
d[ver[i]] = d[x] + 1;
if (ver[i] == t) return 1;
}
}
return 0;
}
long long dinic(long long x, long long flow){
if (x == t) return flow;
long long rest = flow, k;
for (long long i = head[x]; i && rest; i = Next[i]){
if (Edge[i] && d[ver[i]] == d[x] + 1){
k = dinic(ver[i], min(rest, Edge[i]));
if (!k) d[ver[i]] = 0;
Edge[i] -= k;
Edge[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
void dijkstra(){
priority_queue<node> q;
node a;
q.push(node(1, 0));
// isVisited[1] = 1;
memset(d1, 0x3f, sizeof(d1));
d1[1] = 0;
while (!q.empty()){
long long t = q.top().id;
// cout << t << endl;
q.pop();
if (isVisited[t]){
continue;
}
isVisited[t] = 1;
for (edge e:G[t]){
long long y = e.to;
if (d1[y] > d1[t] + e.length){
d1[y] = d1[t] + e.length;
q.push(node(y, d1[y]));
}
}
}
}
int main(int argc, char * argv[])
{
// freopen("1005.in", "r", stdin);
long long T;
scanf("%lld", &T);
while (T--){
maxflow = 0;
tot = 1;
all_edge.clear();
scanf("%lld%lld", &n, &m);
s = 1; t = n;
for (long long i = 1; i <= n; i++){
G[i].clear();
// d1[i] = oo;
isVisited[i] = 0;
}
ms(head);
// ms(ver); ms(Edge); ms(Next); ms(d);
for (long long i = 1; i <= m; i++){
scanf("%lld%lld%lld", &x, &y, &z);
// cout << i << " " << " " << x << " " << y << " " << z << endl;
G[x].push_back(edge(x, y, z));
all_edge.push_back(edge(x, y, z));
}
dijkstra();
for (edge e : all_edge){
if (d1[e.start] + e.length == d1[e.to]){
// G2[e.start].push_back(edge(e.start, e.to, e.length));
// all_edge2.push_back(edge(e.start, e.to, e.length));
add(e.start, e.to, e.length);
}
}
long long flow = 0;
while(bfs()){
while (flow = dinic(s, inf)) maxflow += flow;
}
// cout << maxflow << endl;
printf("%lld\n", maxflow);
}
return 0;
}
网友评论