Problem: Example

Input

2 1
1 2
1 2 1 1


Output

1/2

Solution (in CPP):

Solution:
bool debug=false;
#include <queue>
#include <stdio.h>
#include <vector>
#include <utility>
using namespace std;
#define F first
#define S second
#define PB push_back
const int N=1e2+10;
const int INF=1e9+10;
struct edge{
	int to,rev,cap;
};
vector<edge> graph[N];
int iter[N],dep[N],went[N];
int min(int a,int b){return a>b?b:a;}
void addedge(int u,int v,int cap){
	graph[u].PB({v,(int)graph[v].size(),cap});
	graph[v].PB({u,(int)graph[u].size()-1,0});
	return ;
}
void bfs(int s,int t){
	queue<int> q;
	int nxt;
	iter[s]=dep[s]=0;
	went[s]=t;
	q.push(s);
	while(!q.empty()){
		nxt=q.front();
		q.pop();
		for(edge i:graph[nxt])if(i.cap>0&&went[i.to]!=t){
			went[i.to]=t;
			dep[i.to]=dep[nxt]+1;
			iter[i.to]=0;
			q.push(i.to);
		}
	}
	return ;
}
int dfs(int u,int t,int nv){
	if(u==t)return nv;
	int temp;
	for(int &i=iter[u];i<graph[u].size();i++){
		edge& now=graph[u][i];
		if(now.cap>0&&dep[now.to]>dep[u]){
			temp=dfs(now.to,t,min(nv,now.cap));
			if(temp>0){
				now.cap-=temp;
				graph[now.to][now.rev].cap+=temp;
				return temp;
			}
		}
	}
	return 0;
}
int dinic(int s,int t){
	int ans=0,cnt=0,f;
	for(int i=0;i<N;i++)went[i]=0;
	while(true){
			bfs(s,++cnt);
		if(went[s]!=went[t])break;
		while((f=dfs(s,t,INF))>0)ans+=f;
	}
	return ans;
}
int n;
vector<pair<int,int>> mg[N][N];
pair<__int128,__int128> mcmf(int s,int t){
	pair<int,int> from[N],dp[N],nxt;
	int now=t;
	queue<pair<int,int>> q;
	for(int i=1;i<=n;i++)dp[i]={INF,0};
	dp[s]={0,INF};
	q.push({s,0});
	while(!q.empty()){
		nxt=q.front();
		q.pop();
		if(dp[nxt.F].F<nxt.S)continue;
		for(int i=1;i<=n;i++)for(int j=0;j<mg[nxt.F][i].size();j++)if(mg[nxt.F][i][j].S>0){
			if(dp[i].F>dp[nxt.F].F+mg[nxt.F][i][j].F){
				dp[i].F=dp[nxt.F].F+mg[nxt.F][i][j].F;
				dp[i].S=min(dp[nxt.F].S,mg[nxt.F][i][j].S);
				q.push({i,dp[i].F});
				from[i]={nxt.F,j};
			}
		}
	}
	if(dp[t].S>0)while(now!=s){
		mg[from[now].F][now][from[now].S].S-=dp[t].S;
		mg[now][from[now].F][from[now].S].S+=dp[t].S;
		now=from[now].F;
	}
	return dp[t];
}
__int128 gcd(__int128 a,__int128 b){return b==0?a:gcd(b,a%b);}
void pull(pair<__int128,__int128> &a){
	__int128 temp;
	temp=gcd(a.F,a.S);
	a.F/=temp;
	a.S/=temp;
	return ;
}
int main(){
	int m,s,t,l,r,f,c;
	__int128 temp,F=0,C=0,M;
	pair<__int128,__int128> nxt,lhs,rhs,x,ans;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=0;i<m;i++){
		scanf("%d%d%d%d",&l,&r,&f,&c);
		addedge(l,r,f);
		mg[l][r].PB({c,f});
		mg[r][l].PB({-c,0});
	}
	M=dinic(s,t);
	if(debug)printf("dinic = %d\n",(int)M);
	if(M==0){
	    printf("0/1\n");
	    return 0;
	}
	while(true){
		nxt=mcmf(s,t);
		if(debug)printf("nxt=(%lld,%lld)\n",(long long int)nxt.F,(long long int)nxt.S);
		if(nxt.S<=0)break;
		if(nxt.S*(nxt.F*nxt.F+1)+nxt.F*C+F-M<=0){
			C+=nxt.S*nxt.F;
			F+=nxt.S;
		}
		else if(nxt.F*C+F-M>=0){
			ans={C*C+(M-F)*(M-F),1};
			break;
		}
		else{
			x={M-F-nxt.F*C,nxt.F*nxt.F+1};
			pull(x);
			if(debug)printf("x=(%lld,%lld)\n",(long long int)x.F,(long long int)x.S);
			lhs={x.F*nxt.F,x.S};
			pull(lhs);
			lhs.F+=lhs.S*C;
			lhs={lhs.F*lhs.F,lhs.S*lhs.S};
			if(debug)printf("lhs=(%lld,%lld)\n",(long long int)lhs.F,(long long int)lhs.S);
			rhs=x;
			rhs.F+=F*rhs.S;
			rhs.F=M*rhs.S-rhs.F;
			rhs={rhs.F*rhs.F,rhs.S*rhs.S};
			if(debug)printf("rhs=(%lld,%lld)\n",(long long int)rhs.F,(long long int)rhs.S);
			temp=rhs.S/gcd(rhs.S,lhs.S)*lhs.S;
			ans={lhs.F*(temp/lhs.S)+rhs.F*(temp/rhs.S),temp};
			pull(ans);
			break;
		}
		if(debug)printf("C=%lld F=%lld M=%lld\n",(long long int)C,(long long int)F,(long long int)M);
		if(debug)printf("now ans=%lld\n",(long long int)(C*C+(M-F)*(M-F)));
	}
	printf("%lld/%lld\n",(long long int)ans.F,(long long int)ans.S);
}