Problem: Example

Input

2 1
1 2
1 2 1 1


Output

1/2

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<assert.h>
#define mp make_pair
#define fi first
#define se second
#define cls(a) memset(a,0,sizeof(a))
#define rg 
#define rep(i,x,y) for(rg int i=(x);i<=(y);++i)
#define per(i,x,y) for(rg int i=(x);i>=(y);--i)
using namespace std;
typedef long double real;
typedef unsigned long long LL;
const int N=1000+10,M=20000+10,inf=1e9;
inline LL sqr(LL x){return x*x;}
inline void dn(LL&x,LL y){if(y<x)x=y;}
inline LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
int n,m,s,t;
int maxflow,maxcost;
struct Normal{
	LL a,b;
	Normal(){}
	Normal(LL a,LL b):a(a),b(b){}
	void update(){
		LL d=gcd(a,b);
		a/=d;b/=d;
	}
};
bool operator<(const Normal&a,const Normal&b){
	return a.a*b.b<b.a*a.b;
}
inline void dn(Normal&a,const Normal&b){if(b<a)a=b;}
Normal operator+(const Normal&a,const Normal&b){
	if(a.b==b.b){
		Normal ret=Normal(a.a+b.a,a.b);
		ret.update();
		return ret;
	}
	Normal ret(a.a*b.b+b.a*a.b,a.b*b.b);
	ret.update();
	return ret;
}
Normal operator+(LL a,const Normal&b){
	Normal ret(a*b.b+b.a,b.b);
	ret.update();
	return ret;
}
Normal operator*(LL a,const Normal&b){
	Normal ret(a*b.a,b.b);
	ret.update();
	return ret;
}
Normal operator*(const Normal&a,const Normal&b){
	Normal ret(a.a*b.a,a.b*b.b);
	ret.update();
	return ret;
}
Normal operator-(const Normal&a,LL b){
	Normal ret(a.a-b*a.b,a.b);
	ret.update();
	return ret;
}
inline Normal sqr(const Normal&a){return a*a;}
struct Graph{
	int tot,head[N],to[M],next[M],c[M],w[M],dis[N],f[M],clo,vis[N];
	int c2;
	Graph(){tot=1;}
	void ins(int a,int b,int c,int p){to[++tot]=b;next[tot]=head[a];head[a]=tot;f[tot]=c;w[tot]=p;}
	void addedge(int a,int b,int c,int p){ins(a,b,c,p);ins(b,a,0,-p);}
	int inq[N],q[N],ql,qr;
	bool spfa(){
		rep(i,1,n)dis[i]=inf;++clo;dis[t]=0;
		ql=qr=0;inq[t]=1;q[qr++]=t;
		while(ql!=qr){
			int k=q[ql++];inq[k]=0;if(ql==N)ql=0;
			for(int p=head[k];p;p=next[p])if(c[p^1]&&dis[to[p]]>dis[k]+w[p^1]){
				dis[to[p]]=dis[k]+w[p^1];
				if(inq[to[p]])continue;
				inq[to[p]]=1;
				q[qr++]=to[p];
				if(qr==N)qr=0;
			}
		}
		return dis[s]<inf;
	}
	int dfs(int k,int mf){
		if(k==t)return c2+=mf*dis[s],mf;
		int flow=0,tf;
		vis[k]=clo;
		for(int p=head[k];p&&mf;p=next[p])
			if(c[p]&&vis[to[p]]!=clo&&dis[to[p]]+w[p]==dis[k]&&(tf=dfs(to[p],min(c[p],mf))))
				c[p]-=tf,c[p^1]+=tf,mf-=tf,flow+=tf;
		return flow;
	}
	LL zkwflow(int&fl,int&co,int limit){
		rep(i,2,tot)c[i]=f[i];
		clo=0;cls(vis);c2=0;
		int flow=0,tf;
		while(flow!=limit&&spfa())while((tf=dfs(s,limit-flow)))flow+=tf,++clo;
		fl=flow;co=c2;
		return sqr(co)+sqr(maxflow-fl);
	}
	LL solve(int x){
		int f1,c1,f2,c2;
		LL t1=zkwflow(f1,c1,x);
		zkwflow(f2,c2,x+1);
		int f=maxflow*2-(c2-c1);
		if(f1*2<=f&&f<=f2*2)return sqr(c1+c2)+sqr(2*maxflow-f);
		return t1*4;
	}
	Normal work(){
		rep(i,2,tot)c[i]=f[i];
		clo=0;cls(vis);c2=0;
		int f2=0,tf,c1=0,f1=0;
		Normal ret(sqr(maxflow),1);
		while(spfa())while((tf=dfs(s,1))){
			f1=f2;
			f2+=tf;
			if((LL)f1*(sqr(c2-c1)+1)<=maxflow-(LL)c1*c2+sqr(c1)+sqr(c2-c1)*f1&&maxflow-(LL)c1*c2+sqr(c1)+sqr(c2-c1)*f1<=(LL)f2*(sqr(c2-c1)+1)){
				Normal x(maxflow-(LL)c1*c2+sqr(c1)+sqr(c2-c1)*f1,sqr(c2-c1)+1);
				dn(ret,sqr(c1+(c2-c1)*(x-f1))+sqr(x-maxflow));
			}
			dn(ret,Normal(sqr(c2)+sqr(maxflow-f2),1));
			c1=c2;
			++clo;
		}
		return ret;
	}
}G;
int main(){
//	freopen("code.in","r",stdin);
	scanf("%d%d",&n,&m);
	scanf("%d%d",&s,&t);
	rep(i,1,m){
		int a,b,u,v;scanf("%d%d%d%d",&a,&b,&u,&v);
		G.addedge(a,b,u,v);
	}
	G.zkwflow(maxflow,maxcost,inf);
	int l=0,r=maxflow;
//	while(r-l>5){
//		int dis=(r-l)/3;
//		int m1=l+dis,m2=r-dis;
//		int f1,c1,f2,c2;
//		LL b1=G.zkwflow(f1,c1,m1);
//		LL b2=G.zkwflow(f2,c2,m2);
//		if(b1>b2)l=m1;else r=m2-1;
//	}
//	LL ans=(LL)inf*inf;
//	rep(i,l,r){
//		dn(ans,G.solve(i));
//	}
	Normal x=G.work();
	x.update();
	cout<<x.a<<'/'<<x.b<<endl;
	return 0;
}