衡阳有线宽带网站,宁波seo关键词培训,外贸人员招聘信息,仓库管理系统数据库设计H.Minimum-cost Flow
题目#xff1a;
其实就是给出每条边的单位费用#xff0c;q次查询#xff0c;每次查询改变所有边的容量#xff08;所有边容量一样#xff09;#xff0c;问最后流出1流量的最小花费是多少#xff1f;
题解#xff1a;
暴力做法肯定是每次询问…H.Minimum-cost Flow
题目
其实就是给出每条边的单位费用q次查询每次查询改变所有边的容量所有边容量一样问最后流出1流量的最小花费是多少
题解
暴力做法肯定是每次询问都改一次容量但是肯定会超时想想其他方法 对于题目的每次询问每条增广路的容量为u/v所需最大流是1我们可以列出一个式子 cost(u/v,1) cost(u,v) 也就是把问题变成每条容量为u所需要的最大流为v 为了达到最大流为v的要求肯定有a条增广路容量用完但也肯定会有一个增广路只用了部分假设用了b容量0bu 能得到v a * u b(0bu) 所以我们只需要求出前a条增广路的全部和第a1条增广路的b容量 然后记得判断流出的流量要大于等于v才可以不足v就输出NaN 因为跑得最小费用最大流这样的答案一定是最优答案
代码
#includebits/stdc.husing namespace std;
#define lowbit(x) ((x)(-x))
#define REP(i, a, n) for(int ia;i(n);i)
#define IOS ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int P;const int maxn 1e5 10;
const int N 1e2 10;
const int M 1e3 10;
const int inf 0x3f3f3f3f;
const ll INF 0x3f3f3f3f3f3f3f3f;
const int mod 1e9 7;
const int mod2 998244353;
const int mod3 1e9 9;
const int hash1 131;
const int hash2 13331;
const double eps 1e-6;
int head[N], ver[M], nxt[M], edge[M], cost[M];
int tot 1;
int d[N], incf[N], pre[N];
int vis[N];void add(int x, int y, int z, int c)
{ver[tot] y, edge[tot] z, cost[tot] c, nxt[tot] head[x], head[x] tot;ver[tot] x, edge[tot] 0, cost[tot] -c, nxt[tot] head[y], head[y] tot;
}int s, t;
vectorint path;bool spfa()
{queueint q;memset(d, inf, sizeof(d));memset(vis, 0, sizeof(vis));q.push(s);d[s] 0, vis[s] 1;incf[s] 1 30;while (!q.empty()){int x q.front();q.pop();vis[x] 0;for (int i head[x]; i; i nxt[i]){if (!edge[i])continue;int y ver[i];if (d[y] d[x] cost[i]){d[y] d[x] cost[i];incf[y] min(incf[x], edge[i]);pre[y] i;if (!vis[y])vis[y] 1, q.push(y);}}}if (d[t] inf)return false;return d[t];
}int maxflow, ans;void update()
{path.push_back(d[t]);//记录每条增广路的花费int x t;while (x ! s){int i pre[x];edge[i] - incf[t];edge[i ^ 1] incf[t];x ver[i ^ 1];}maxflow incf[t];ans d[t] * incf[t];}ll sumd[N];int main()
{int n, m;while (scanf(%d%d, n, m) ! EOF){path.clear();memset(head, 0, sizeof(head));tot 1;for (int i 1; i m; i){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, 1, c);}s 1, t n;while (spfa())update();for (int i 0; i path.size(); i){sumd[i 1] sumd[i] path[i];//前i条增广路的花费 }int q;scanf(%d, q);int u, v;for (int i 1; i q; i){scanf(%d%d, u, v);if (u * path.size() v){puts(NaN);continue;}ll a v / u;ll b v % u;ll ans sumd[a] * u path[a] * b;ll x __gcd((ll) v, ans);printf(%lld/%lld\n, ans / x, v / x);}}return 0;
}
