Problem: Example

Input

2 1
1 2
1 2 1 1


Output

1/2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=110,M=1010,inf=1e9;
struct E{int v,nxt,w,c;}e[2010];
int n,m,s,t,sf,sc,cc=1,tt,ff,hd[N],d[N],vis[N],pre[N];ll wx,wy;queue<int>q;
struct st{ll x,y;}o,a[100005];
inline st operator-(st a,st b){return (st){a.x-b.x,a.y-b.y};}
inline void add(int u,int v,int w,int c){e[++cc]=(E){v,hd[u],w,c};hd[u]=cc;e[++cc]=(E){u,hd[v],0,-c};hd[v]=cc;}
inline bool spfa()
{
	for(int i=1;i<=n;++i)d[i]=inf,vis[i]=0;
	d[s]=0;q.push(s);vis[s]=1;
	while(!q.empty())
	{
		int x=q.front();q.pop();vis[x]=0;
		for(int i=hd[x];i;i=e[i].nxt)if(e[i].w)
		{
			int y=e[i].v,z=d[x]+e[i].c;
			if(d[y]>z)
			{
				d[y]=z;pre[y]=i;
				if(!vis[y])q.push(y),vis[y]=1;
			}
		}
	}
	if(d[t]>=inf)return 0;
	int flw=inf;
	for(int x=t;x!=s;x=e[pre[x]^1].v)flw=min(flw,e[pre[x]].w);
	for(int x=t;x!=s;x=e[pre[x]^1].v)e[pre[x]].w-=flw,e[pre[x]^1].w+=flw;
	sf+=flw;sc+=flw*d[t];return 1;
}
inline ll F(st a,st b){return a.x*b.x+a.y*b.y;}
inline ll G(st a,st b){return a.x*b.y-a.y*b.x;}
inline ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
inline void ans(ll x,ll y)
{
	ll g=gcd(x,y);x/=g;y/=g;
	if(!ff||wx*y>x*wy)wx=x,wy=y,ff=1;
}
inline void sol(st a,st b)
{
	if(F(a,a-b)<=0||F(b,b-a)<=0)return;
	ans(G(a,b)*G(a,b),F(a-b,a-b));
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1,u,v,w,c;i<=m;++i){scanf("%d%d%d%d",&u,&v,&w,&c);add(u,v,w,c);}
	a[tt=0]=(st){0,0};
	while(spfa())a[++tt]=(st){sf,sc};
	o=(st){sf,0};
	for(int i=0;i<=tt;++i){a[i]=a[i]-o;ans(F(a[i],a[i]),1);}
	for(int i=0;i<tt;++i)sol(a[i],a[i+1]);
	printf("%lld/%lld\n",wx,wy);
	return 0;
}