题意:给定一个n个点和m条边的有向图,没经过一条边就会消耗一定体力但会获得一些体能
要求从1号点到n号点的消耗的最少体力获得的最大体能
解题方法:我们先跑一遍dijkstra,然后将得到的最短路图给扣出来,在上面求出来最大的第二权值
这样就保证了第一权值始终是最短的了。我们想采用拓扑序求解,但是题目中的权值是可以取到零的
我们扣最短路图的时候就可能出现零环,导致我们的图就不是DAG了,所以我们还要缩点,删去零环这部分
最后在拓扑图上求最大的第二权值
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define int long long
const int N = 5e5 + 10,M = 4 * N,INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int>PII;
#define x first
#define y second
int h1[N],h2[N],h3[N],e[M],ne[M],w1[M],w2[N],idx;
int dfn[N],low[N],timestamp;
int stk[N],top,scc_cnt,id[N];
bool in_stk[N],st[N];
int dist[N],value[N];
int n,m;
void add(int h[],int a,int b,int c,int d)
{
e[idx] = b,w1[idx] = c,w2[idx] = d,ne[idx] = h[a],h[a] = idx ++;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
priority_queue<PII,vector<PII>,greater<PII>>q;
dist[1] = 0;
q.push({0, 1});
while(!q.empty())
{
auto t = q.top();
q.pop();
int ver = t.y,distance = t.x;
if(st[ver])continue;
st[ver] = true;
for(int i = h1[ver]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w1[i])
{
dist[j] = distance + w1[i];
q.push({dist[j], j});
}
}
}
for(int i = 1; i <= n; i ++)
{
if(dist[i] == INF)continue;
for(int j = h1[i]; ~j; j = ne[j]){
int k = e[j];
if(dist[k] == dist[i] + w1[j])
add(h2,i, k, w1[j], w2[j]);
}
}
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[++ top] = u,in_stk[u] = true;
for(int i = h2[u]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if(in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if(dfn[u] == low[u])
{
int yy;
++ scc_cnt;
do{
yy = stk[top --];
id[yy] = scc_cnt;
in_stk[yy] = false;
}while(yy != u);
}
}
void solve()
{
cin >> n >> m;
for(int i = 0; i <= n + 10; i ++)
{
h1[i] = h2[i] = h3[i] = -1;
dfn[i] = low[i] = stk[i] = id[i] = 0;
in_stk[i] = false;
}
timestamp = idx = scc_cnt = 0;
memset(value, 0, sizeof value);
for(int i = 0; i < m; i ++)
{
int a,b,c,d;cin >> a >> b >> c >> d;
add(h1,a,b,c,d);
}
dijkstra();
for(int i = 1; i <= n; i ++)
if(!dfn[i])tarjan(i);
for(int i = 1; i <= n; i ++)
for(int j = h2[i]; ~j; j = ne[j]){
int k = e[j];
int a = id[i],b = id[k];
if(a != b)add(h3, a, b, w1[j], w2[j]);
}
for(int i = scc_cnt; i; i --)
for(int j = h3[i]; ~j; j = ne[j]){
int k = e[j];
if(value[k] < value[i] + w2[j])
value[k] = value[i] + w2[j];
}
cout << dist[n] << " " << value[id[n]] << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
有一个长度是n的数组,我们的操作是每次可以使长度是k的一段加上1
并且给定我们一些区间使得这段区间内的sum要满足条件
由于条件很多,想到差分约束.
设a[i]表示前i座塔的魔法成分
1. 假设当前塔是i,那么i要满足区间(i-k+1,i+k-1)的魔法成分>=q[i]
a[i+k-1] - a[i-k] >= p[i],p[i]是i这个点所需的魔法总量
2. 由于我们的操作都是正数,所以有后面一定大于等于前面
a[i] >= a[i-1]
3. 我们还有给定的约束要满足
a[l-1] >= a[r]-b
由以上差分约束关系建图,如果dist[n]=0,那么就无解,否则输出dist[n]
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 1e4 + 10,M = 3e5 + 10;
typedef long long LL;
//#define int long long
typedef pair<int,int>PII;
#define x first
#define y second
int h[N],e[M],ne[M],w[M],idx;
int dist[N],cnt[N];
bool st[N];
int p[N];
int n,k;
void add(int a,int b,int c)
{
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}
bool spfa()
{
memset(dist, -0x3f, sizeof dist);
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
queue<int>q;
q.push(0);
dist[0] = 0;
st[0] = true;
while(!q.empty())
{
auto t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] < dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n + 1)return true;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
void solve()
{
cin >> n >> k;
idx = 0;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i ++)
{
cin >> p[i];
//可能会出现越界情况
add(max(0, i - k), min(i + k - 1, n), p[i]);
add(i - 1, i, 0);
}
int q;cin >> q;
while(q --)
{
int l,r,b;cin >> l >> r >> b;
add(r, l - 1, -b);
}
if(spfa())cout << -1 << endl;
else cout << dist[n] << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}
Link with Equilateral Triangle
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 1e4 + 10,M = 3e5 + 10;
typedef long long LL;
//#define int long long
typedef pair<int,int>PII;
#define x first
#define y second
void solve()
{
int n;cin >> n;
cout << "No" << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}