在第i个点只能选A[i]次的情况下,能选出多少条1-n的最短路
Solution
我们造出最短路DAG，然后对每个点拆点限流，跑最大流即可
双向边警告！（有悖直觉
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace sp {
// Interfaces: n, g[][], spt[], d[]
const int N = 200005;
int n;
struct edge {int u,v,w;};
vector<pair<int, int> >g[N];
vector<edge> spt;
int d[N], v[N];
void make(int t1, int t2, int t3) {
g[t1].push_back(make_pair(t2, t3));
}
void reset_graph() {
for (int i = 0; i <= n; i++)
g[i].clear();
}
void reset_solver() {
memset(d, 0x3f, sizeof d);
memset(v, 0x00, sizeof v);
}
void solve(int v0) {
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
reset_solver();
d[v0] = 0;
q.push(make_pair(0,v0));
while (q.size()) {
pair<int, int> p = q.top();
int dis = p.first;
int pos = p.second;
q.pop();
v[pos] = 1;
for (int i = 0; i < g[pos].size(); i++) {
int x = g[pos][i].first;
int y = g[pos][i].second;
if (d[x] > d[pos] + y) {
d[x] = d[pos] + y;
if (!v[x]) q.push(make_pair(d[x], x));
}
}
}
for(int i=1;i<=n;i++) {
int p=i;
for(int j=0;j<g[p].size();j++) {
int q=g[p][j].first, w=g[p][j].second;
if(d[q]==d[p]+w) spt.push_back((edge){p,q,w});
}
}
}
}
namespace flow {
const int maxn = 200005;
const int inf = 1e+14;
int dis[maxn], ans, cnt = 1, s, t, pre[maxn * 10], nxt[maxn * 10], h[maxn], v[maxn * 10];
std::queue<int> q;
void make(int x, int y, int z) {
pre[++cnt] = y, nxt[cnt] = h[x], h[x] = cnt, v[cnt] = z;
pre[++cnt] = x, nxt[cnt] = h[y], h[y] = cnt;
}
bool bfs() {
memset(dis, 0, sizeof dis);
q.push(s), dis[s] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = h[x]; i; i = nxt[i])
if (!dis[pre[i]] && v[i])
dis[pre[i]] = dis[x] + 1, q.push(pre[i]);
}
return dis[t];
}
int dfs(int x, int flow) {
if (x == t || !flow)
return flow;
int f = flow;
for (int i = h[x]; i; i = nxt[i])
if (v[i] && dis[pre[i]] > dis[x]) {
int y = dfs(pre[i], min(v[i], f));
f -= y, v[i] -= y, v[i ^ 1] += y;
if (!f)
return flow;
}
if (f == flow)
dis[x] = -1;
return flow - f;
}
int solve(int _s,int _t) {
s=_s;
t=_t;
ans = 0;
for (; bfs(); ans += dfs(s, inf));
return ans;
}
}
const int N = 5005;
int n,m,t1,t2,t3,lim[N];
signed main() {
scanf("%lld%lld",&n,&m);
sp::n=n;
for(int i=1;i<=m;i++) {
scanf("%lld%lld%lld",&t1,&t2,&t3);
sp::make(t1,t2,t3);
sp::make(t2,t1,t3);
}
sp::solve(1);
//for(int i=1;i<=n;i++) cout<<sp::d[i]<<" ";
//cout<<endl;
for(int i=0;i<sp::spt.size();i++) {
int u=sp::spt[i].u, v=sp::spt[i].v, w=sp::spt[i].w;
flow::make(2*u,2*v-1,1e+14);
}
for(int i=1;i<=n;i++) {
scanf("%lld",&lim[i]);
flow::make(2*i-1,2*i,lim[i]);
}
cout<<flow::solve(2,2*n-1);
}
我的模板丑的不行了，我得去改造模板了