Problem: Example

Input

2 1
1 2
1 2 1 1


Output

1/2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define INF 10000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

struct mincostflow{
	struct edge{
		int to,cap,cost,rev;
		edge(int t,int c,int co,int r){
			to=t;
			cap=c;
			cost=co;
			rev=r;
		}
	};
	vector<edge> G[205];
	int h[205];
	int dist[205];
	int prevv[205],preve[205];
	void add_edge(int from,int to,int cap,int cost){
		G[from].push_back(edge(to,cap,cost,G[to].size()));
		G[to].push_back(edge(from,0,-cost,G[from].size()-1));
	}
	int min_cost_flow(int s,int t,int f,int V){
		int res=0;
		fill(h,h+V,0);
		while(f>0){
			priority_queue<P,vector<P>,greater<P> > que;
			fill(dist,dist+V,INF);
			dist[s]=0;
			que.push(P(0,s));
			while(que.size()){
				P p=que.top();
				que.pop();
				int v=p.second;
				if(dist[v]<p.first)continue;
				for(int i=0;i<G[v].size();i++){
					edge &e=G[v][i];
					if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
						dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
						prevv[e.to]=v;
						preve[e.to]=i;
						que.push(P(dist[e.to],e.to));
					}
				}
			}
			if(dist[t]==INF)return -1;
			for(int v=0;v<V;v++){
				h[v]+=dist[v];
			}
			int d=f;
			for(int v=t;v!=s;v=prevv[v]){
				d=min(d,G[prevv[v]][preve[v]].cap);
			}
			f-=d;
			res+=d*h[t];
			for(int v=t;v!=s;v=prevv[v]){
				edge &e=G[prevv[v]][preve[v]];
				e.cap-=d;
				G[v][e.rev].cap+=d;
			}
		}
		return res;
	}
};


class dinic{
public:
	struct edge{
		int to,cap,rev;
		edge(){}
		edge(int tt,int cc,int rr){
			to=tt;
			cap=cc;
			rev=rr;
		}
	};
	vector<edge> G[301];
	int level[301];
	int iter[301];
	void add_edge(int from,int to,int cap){
		G[from].push_back(edge(to,cap,G[to].size()));
		G[to].push_back(edge(from,0,G[from].size()-1));
	}

	void bfs(int s){
		memset(level,-1,sizeof(level));
		queue<int> que;
		level[s]=0;
		que.push(s);
		while(que.size()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>0 && level[e.to]<0){
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}
	}

	int dfs(int v,int t,int f){
		if(v==t)return f;
		int res=0;
		for(int &i=iter[v];i<G[v].size();i++){
			edge &e=G[v][i];
			if(e.cap>0 && level[v]<level[e.to]){
				int d=dfs(e.to,t,min(e.cap,f));
				if(d>0){
					e.cap-=d;
					G[e.to][e.rev].cap+=d;
					res+=d;
					f-=d;
					if(f==0)break;
				}
			}
		}
		return res;
	}

	int max_flow(int s,int t){
		int flow=0;
		while(1){
			bfs(s);
			if(level[t]<0)return flow;
			memset(iter,0,sizeof(iter));
			int f;
			while((f=dfs(s,t,INF))>0){
				flow+=f;
			}
		}
	}
};

mincostflow mi;
dinic di;

ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}

int n;
int S,T;

ll labs(ll v){
	if(v<0LL)return -v;
	return v;
}

P solve(ll m){
	ll sum=0;
	for(int i=0;i<m;i++){
		ll c=mi.min_cost_flow(S,T,1,n);
		if(m-i-c*sum<=0){
			return P(sum*sum+(m-i)*(m-i),1LL);
		}
		if(m-i-c*sum>=c*c+1LL){
			sum+=c;
		}else{
			ll x=m-i-c*sum;
			ll v1=x*x;
			ll v2=x*(2*c*sum-2*m+2*i);
			ll res=v1+v2;
			res+=(c*c+1)*(m*m+i*i+sum*sum-2*m*i);
			ll res2=(c*c+1);
			ll g=gcd(res,res2);
			res/=g;
			res2/=g;
			return P(res,res2);
		}
	}
	return P(sum*sum,1LL);
}

int main(void){
	int m;
	scanf("%d%d",&n,&m);
	scanf("%d%d",&S,&T);
	S--;
	T--;
	for(int i=0;i<m;i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		a--;
		b--;
		mi.add_edge(a,b,c,d);
		di.add_edge(a,b,c);
	}
	ll maxi=di.max_flow(S,T);
	P res=solve(maxi);
	printf("%lld/%lld\n",res.first,res.second);
	return 0;
}