1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
inline int Read(){ register int r=0,c=getchar(); while(c<'0' || '9'<c) c=getchar(); while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar(); return r; }
const int N=510,M=5e4+10; #define ci const int &
struct GRAPH{ int head[N],to[M<<1],nxt[M<<1],cap[M<<1],cst[M<<1],ncnt; GRAPH(){ncnt=1;} void AddEdge(ci u,ci v,ci ca,ci cs){ int p=++ncnt,q=++ncnt; to[p]=v,nxt[p]=head[u],cap[p]=ca,cst[p]=cs,head[u]=p; to[q]=u,nxt[q]=head[v],cap[q]=0,cst[q]=-cs,head[v]=q; } inline int operator [](ci u){return head[u];} }Gr;
int n,m; vector<long long> aug,pre; bool inq[N]; int to[N],eid[N]; long long dis[N];
queue<int> que; bool SPFA(){ memset(dis,0x3f,sizeof dis); long long inf=dis[0]; que.push(1),dis[1]=0; while(!que.empty()){ int u=que.front();que.pop(); inq[u]=false; for(int it=Gr[u];it;it=Gr.nxt[it]){ int v=Gr.to[it]; if(Gr.cap[it]<=0 || dis[v]<=dis[u]+Gr.cst[it]) continue; dis[v]=dis[u]+Gr.cst[it]; to[v]=u,eid[v]=it; if(!inq[v]) inq[v]=true,que.push(v); } } return dis[n]<inf; } void Dinic(){ while(SPFA()){ int s=n; long long tot=0; while(s!=1){ tot+=Gr.cst[eid[s]]; Gr.cap[eid[s]]--,Gr.cap[eid[s]^1]++; s=to[s]; } aug.push_back(tot); } } long long GCD(long long a,long long b){return b? GCD(b,a%b):a;} int main(){ freopen("water.in","r",stdin); freopen("water.out","w",stdout); n=Read(),m=Read(); for(int i=1;i<=m;i++){ int u=Read(),v=Read(),w=Read(); Gr.AddEdge(u,v,1,w); } Dinic(); if(!aug.empty()){ sort(aug.begin(),aug.end()); pre.push_back(aug.front()); for(int i=1,I=aug.size();i<I;i++) pre.push_back(pre.back()+aug[i]); } int cas=Read(); while(cas--){ int x=Read(),y=Read(); if((long long)aug.size()*x<y){printf("-1\n");continue;} long long p=y/x? 1ll*x*pre[y/x-1]:0,q=y; if(y%x) p+=1ll*aug[y/x]*(y%x); long long gcd=GCD(p,q); p/=gcd,q/=gcd; printf("%lld/%lld\n",p,q); } return 0; }
|