这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 | |||
2020-2021:teams:wangzai_milk:20200712比赛记录 [2020/07/15 13:14] zars19 [A - B-Suffix Array] |
2020-2021:teams:wangzai_milk:20200712比赛记录 [2020/07/16 15:15] (当前版本) wzx27 |
||
---|---|---|---|
行 316: | 行 316: | ||
</code></hidden> | </code></hidden> | ||
\\ | \\ | ||
+ | |||
+ | ==== H - Minimum-cost Flow ==== | ||
+ | |||
+ | 费用流建图,每条边的费用已知,容量在每次询问时给出,每次询问求流出 $1$ 单位的最小费用。 | ||
+ | |||
+ | 可以先假设每条边容量为 $1$ ,每次给出具体容量时再做调整。 | ||
+ | 具体做的时候不知道哪里被卡了一直 $t$ ,改了很久才过(快读+dij费用流)。 | ||
+ | |||
+ | <hidden code> <code cpp> | ||
+ | #pragma GCC optimize(3,"Ofast","inline") | ||
+ | #include<bits/stdc++.h> | ||
+ | #define ALL(x) (x).begin(),(x).end() | ||
+ | #define ll long long | ||
+ | #define ull unsigned long long | ||
+ | #define pii_ pair<int,int> | ||
+ | #define mp_ make_pair | ||
+ | #define pb push_back | ||
+ | #define fi first | ||
+ | #define se second | ||
+ | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
+ | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
+ | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
+ | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
+ | using namespace std; | ||
+ | const ll INF = 1LL<<60; | ||
+ | const int inf = 1<<30; | ||
+ | const int maxn = 2005; | ||
+ | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
+ | inline int read(){ | ||
+ | int s=0,w=1; | ||
+ | char ch=getchar(); | ||
+ | while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} | ||
+ | while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); | ||
+ | return s*w; | ||
+ | } | ||
+ | ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);} | ||
+ | ll sum[maxn]; | ||
+ | int n,m,q,num; | ||
+ | int head[maxn],dis[maxn],h[maxn],PrePoint[maxn],PreEdge[maxn]; | ||
+ | vector<int> mcost; | ||
+ | struct node | ||
+ | { | ||
+ | int u,v,f,w,nxt; | ||
+ | }edge[maxn]; | ||
+ | inline void addedge(int x,int y,int f,int z) | ||
+ | { | ||
+ | edge[num].u=x; | ||
+ | edge[num].v=y; | ||
+ | edge[num].f=f; | ||
+ | edge[num].w=z; | ||
+ | edge[num].nxt=head[x]; | ||
+ | head[x]=num++; | ||
+ | } | ||
+ | void add(int u,int v,int w,int c) | ||
+ | { | ||
+ | addedge(u,v,w,c); | ||
+ | addedge(v,u,0,-c); | ||
+ | } | ||
+ | int MCMF(int s,int t) | ||
+ | { | ||
+ | int ansflow=0; | ||
+ | rep(i,1,n) h[i] = 0; | ||
+ | while(1) | ||
+ | { | ||
+ | priority_queue<pii_>q; | ||
+ | rep(i,1,n) dis[i] = inf; | ||
+ | dis[s]=0; | ||
+ | q.push(make_pair(0,s)); | ||
+ | while(q.size()!=0) | ||
+ | { | ||
+ | pii_ p=q.top();q.pop(); | ||
+ | if(-p.fi!=dis[p.se]) continue; | ||
+ | if(p.se==t) break; | ||
+ | for(int i=head[p.se];i!=-1;i=edge[i].nxt) | ||
+ | { | ||
+ | int nowcost=edge[i].w+h[p.se]-h[edge[i].v]; | ||
+ | if(edge[i].f>0&&dis[edge[i].v]>dis[p.se]+nowcost) | ||
+ | { | ||
+ | dis[edge[i].v]=dis[p.se]+nowcost; | ||
+ | q.push(make_pair(-dis[edge[i].v],edge[i].v)); | ||
+ | PrePoint[edge[i].v]=p.se; | ||
+ | PreEdge[edge[i].v]=i; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | if(dis[t]==inf) break; | ||
+ | for(int i=1;i<=n;i++) h[i]+=dis[i]; | ||
+ | int nowflow=inf; | ||
+ | for(int now=t;now!=s;now=PrePoint[now]) | ||
+ | nowflow=min(nowflow,edge[PreEdge[now]].f); | ||
+ | for(int now=t;now!=s;now=PrePoint[now]) | ||
+ | edge[PreEdge[now]].f-=nowflow, | ||
+ | edge[PreEdge[now]^1].f+=nowflow; | ||
+ | ansflow+=nowflow; | ||
+ | mcost.pb(h[t]); | ||
+ | } | ||
+ | return ansflow;; | ||
+ | } | ||
+ | int main() | ||
+ | { | ||
+ | //fastio(); | ||
+ | ll u,v,c; | ||
+ | while(~scanf("%d%d",&n,&m)){ | ||
+ | rep(i,1,n) head[i] = -1; | ||
+ | num = 2; | ||
+ | mcost.clear(); | ||
+ | int s = 1,t = n; | ||
+ | rep(i,1,m){ | ||
+ | u = read(); | ||
+ | v = read(); | ||
+ | c = read(); | ||
+ | add(u,v,1,c); | ||
+ | } | ||
+ | int maxflow = MCMF(s,t); | ||
+ | sort(ALL(mcost)); | ||
+ | //for(int x:mcost) show1(x); | ||
+ | int sz = mcost.size(); | ||
+ | rep(i,1,sz) sum[i] = sum[i-1] + mcost[i-1]; | ||
+ | int q = read(); | ||
+ | while(q--){ | ||
+ | u = read();v = read(); | ||
+ | if(u*maxflow<v) printf("NaN\n"); | ||
+ | else{ | ||
+ | int L = 1,R = sz,pos; | ||
+ | while(L<=R){ | ||
+ | int mid = (L+R)>>1; | ||
+ | if(u*mid >= v) pos = mid,R=mid-1; | ||
+ | else L = mid+1; | ||
+ | } //show1(pos); | ||
+ | ll a = u*sum[pos-1]; | ||
+ | ll o = (v-u*(pos-1)) * (sum[pos] - sum[pos-1]); //show2(a,o); | ||
+ | a = a+o; | ||
+ | ll g = gcd(a,v); | ||
+ | a /= g, v /= g; | ||
+ | printf("%lld/%lld\n",a,v); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
+ | </code> <hidden> | ||
+ | \\ | ||
+ | |||
==== J - Easy Integration ==== | ==== J - Easy Integration ==== | ||