提出 #486936

---

ソースコード 拡げる

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>
#define E 1010
#define V 110
using namespace std;
struct frac{
	long long n;
	long long d;
	frac(long long _n=0,long long _d=1):n(_n),d(_d){long long g=gcd(n,d); n/=g; d/=g;}
	long long gcd(long long a,long long b)const{
		if(a<0) a=-a;
		if(b<0) b=-b;
		while(b){
			a%=b;
			a^=b;
			b^=a;
			a^=b;
		}
		return a;
	}
	long long int_part()const{return n>=0?n/d:(n-d+1)/d;}
	long long frac_part()const{return n%d>=0?n%d:n%d+d;}
	frac operator+(frac rhs)const{
		long long g=gcd(d,rhs.d);
		return frac(n*(rhs.d/g)+rhs.n*(d/g),d/g*rhs.d);
	}
	frac operator-(frac rhs)const{return operator+(frac(-rhs.n,rhs.d));}
	frac operator*(frac rhs)const{
		long long g1=gcd(n,rhs.d),g2=gcd(rhs.n,d);
		return frac((n/g1)*(rhs.n/g2),(d/g2)*(rhs.d/g1));
	}
	bool less(frac rhs)const{
		if(int_part()<rhs.int_part()) return true;
		else if(int_part()>rhs.int_part()) return false;
		if(!frac_part()||!rhs.frac_part()) return rhs.frac_part();
		return frac(rhs.d,rhs.frac_part()).less(frac(d,frac_part()));
	}
	bool operator<(long long x)const{return int_part()<x;}
	bool operator>(long long x)const{return int_part()>x||int_part()==x&&frac_part();}
	frac sq()const{return (*this)*(*this);}
};
int to[E<<1],w[E<<1],c[E<<1],nxt[E<<1],src,dst,cnt;
int head[V],in[V],from[V],mf[V];
long long dis[V];
void init(int s,int t){
	src=s;
	dst=t;
	memset(head,-1,sizeof(head));
	cnt=0;
}
void add_edge(int u,int v,int _w,int _c){
	to[cnt]=v;
	to[cnt|1]=u;
	c[cnt]=_c;
	c[cnt|1]=0;
	w[cnt]=_w;
	w[cnt|1]=-_w;
	nxt[cnt]=head[u];
	nxt[cnt|1]=head[v];
	head[u]=cnt;
	head[v]=cnt|1;
	cnt+=2;
}
bool sp(long long &flow,long long &cost){
	queue<int> q;
	memset(dis,0x3f,sizeof(dis));
	long long inf=dis[0];
	memset(in,0,sizeof(in));
	memset(from,0,sizeof(from));
	q.push(src);
	in[src]=1;
	dis[src]=0;
	mf[src]=inf;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		in[u]=0;
		for(int i=head[u];i!=-1;i=nxt[i]){
			if(!c[i]) continue;
			int v=to[i];
			if(dis[u]+w[i]<dis[v]){
				from[v]=i;
				dis[v]=dis[u]+w[i];
				mf[v]=min(mf[u],c[i]);
				if(!in[v]){
					q.push(v);
					in[v]=1;
				}
			}
		}
	}
	flow=mf[dst];
	cost=dis[dst];
	if(cost<inf){
		for(int u=dst;u!=src;u=to[from[u]^1]){
			c[from[u]]-=flow;
			c[from[u]^1]+=flow;
		}
		return true;
	}
	return false;
}
frac solve(){
	vector<long long> vf,vc;
	long long cost=0,flow=0,af,ac;
	while(sp(af,ac)){
		flow+=af;
		vf.push_back(af);
		vc.push_back(ac);
	}
	frac ans(flow*flow);
	for(int i=0;i<vf.size();i++){
		frac mp(flow-vc[i]*cost,vc[i]*vc[i]+1);
		if(mp<vf[i]&&mp>0){
			frac tmp=frac(cost*cost+flow*flow)+mp*frac(2*cost*vc[i]-2*flow)+mp*frac(flow-vc[i]*cost);
			if(tmp.less(ans)) ans=tmp;
		}
		flow-=vf[i];
		cost+=vc[i]*vf[i];
		if(ans>flow*flow+cost*cost){
			ans=frac(flow*flow+cost*cost);
		}
	}
	return ans;
}
int main(){
	int n,m,s,t,u,v,_w,_c;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	init(s,t);
	while(m--){
		scanf("%d%d%d%d",&u,&v,&_c,&_w);
		add_edge(u,v,_w,_c);
	}
	frac ans=solve();
	printf("%lld/%lld\n",ans.n,ans.d);
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:132:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&n,&m,&s,&t);
                               ^
./Main.cpp:135:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&u,&v,&_c,&_w);
                                  ^

ジャッジ結果