QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123163#602. 最小费用最大流(随机数据)c20231020#0 0ms0kbC++234.1kb2023-07-11 20:17:242023-07-11 20:17:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 20:17:25]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-07-11 20:17:24]
  • 提交

answer

#define poj
#define zcz
#ifdef poj
//C++
#include<iomanip>
#include<iostream>
//C
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
//STL
#include<algorithm>
#include<bitset>
#include<functional>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
//C++11
#if __cplusplus>=201103L
#include<chrono>
#include<random>
#include<unordered_set>
#include<unordered_map>
#endif
#else
#include<bits/stdc++.h>
#endif
using namespace std;
#ifdef zcz
class fastin{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *inf;
	char *inbuf,*inst,*ined;
	inline char _getchar(){
		if(inst==ined)inst=inbuf,ined=inbuf+fread(inbuf,1,MAXBF,inf);
		return inst==ined?EOF:*inst++;
	}
	public:
	fastin(FILE*_inf=stdin){
		inbuf=new char[MAXBF],inf=_inf,inst=inbuf,ined=inbuf;
	}
	~fastin(){delete inbuf;}
	template<typename Int> fastin&operator>>(Int &n){
		static char c;
		Int t=1;
		while((c=_getchar())<'0'||c>'9')if(c=='-')t=-1;
		n=(c^48);
		while((c=_getchar())>='0'&&c<='9')n=(n<<3)+(n<<1)+(c^48);
		n*=t;
		return *this;
	}
	fastin&operator>>(char*s){
		int t=0;
		static char c;
		while((c=_getchar())==' '||c=='\n');
		s[t++]=c;
		while((c=_getchar())>='!'&&c<='~')s[t++]=c;
		s[t]='\0';
		return *this;
	}
}fi;
class fastout{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *ouf;
	char *oubuf,*oust,*oued;
	inline void _flush(){fwrite(oubuf,1,oued-oust,ouf);oued=oust;}
	inline void _putchar(char c){
		if(oued==oust+MAXBF)_flush(),oued=oubuf;
		*oued++=c;
		#ifdef local
		_flush();
		#endif
	}
	public:
	fastout(FILE*_ouf=stdout){
		oubuf=new char[MAXBF],ouf=_ouf,oust=oubuf,oued=oubuf;
	}
	~fastout(){_flush();delete oubuf;}
	template<typename Int> fastout&operator<<(Int n){
		if(n<0)_putchar('-'),n=-n;
		static char S[20];
		int t=0;
		do{S[t++]='0'+n%10,n/=10;}while(n);
		for(int i=0;i<t;++i)_putchar(S[t-i-1]);
		return *this;
	}
	fastout&operator<<(char c){_putchar(c);return *this;}
	fastout&operator<<(char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
	fastout&operator<<(const char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
}fo;
#define cin fi
#define cout fo
#else
#define czc ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#endif
#define mod 1000000007
#define ll long long
#define isinf 0x3f3f3f3f
#define ilinf 0x7fffffff
#define lsinf 0x3f3f3f3f3f3f3f3f
#define llinf 0x7fffffffffffffff
#define pii pair<int,int>
#define fr first
#define sc second
#define next ___
#define pb push_back
#define N 5010
#define M 100010
#define For(i,a,b) for(int i=(a);i<=(b);++i)
int n,m,ttt[N],r[N],s,t,ans,next[M],to[M],w[M],p[M],tot=1,h[N],c[N],cur[N],dis[N],vis[N],re[N],d[N];
void add(int x,int y,int z,int v){
//	cout<<x<<' '<<y<<' '<<z<<' '<<v<<'\n';
	to[++tot]=y;next[tot]=h[x];w[tot]=z;p[tot]=v;h[x]=tot;
	to[++tot]=x;next[tot]=h[y];w[tot]=0;p[tot]=-v;h[y]=tot;
	return;
}
int bfs(){
	fill(c,c+n+1,isinf);fill(dis,dis+n+1,isinf);fill(vis,vis+n+1,0);
	for(int i=1;i<=n;++i)cur[i]=h[i];
	queue<int>q;q.push(s);dis[s]=0;
	while(q.size()){
		int x=q.front();q.pop();vis[x]=0;
		for(int i=h[x];i;i=next[i]){
			int y=to[i],z=w[i],va=p[i];
			if(dis[y]>dis[x]+va&&z){
				dis[y]=dis[x]+va;re[y]=i;
				c[y]=min(c[x],z);
				if(!vis[y])vis[y]=1,q.push(y);
			}
		}
	}
	fill(vis,vis+t+1,0);
	return c[t]!=isinf;
}
int dfs(int x,int v){
	if(x==t||!v)return v;
	int tem=v;vis[x]=1;
	for(int i=cur[x];i;i=next[i]){
		cur[x]=i;
		int y=to[i],z=w[i];
		if(vis[y]||dis[y]!=dis[x]+p[i])continue;
		int vt=dfs(y,min(tem,z));
		if(!vt)continue;
		w[i]-=vt;w[i^1]+=vt;
		tem-=vt;ans+=vt*p[i];
		if(tem==0)break;
	}
	vis[x]=0;
	return v-tem;
}
void solve(){
	cin>>n>>m>>s>>t;
	For(i,1,m){
		int u,v,w,p;
		cin>>u>>v>>w>>p;
		add(u,v,w,p);
	}
	int y=0;
	while(bfs())y+=dfs(s,isinf);
	cout<<y<<' '<<ans<<'\n';
	return;
}
int main(){
	#ifndef zcz
	czc;
	#endif
	int t=1;
	while(t--)solve();
	return 0;
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

8 27
2 3 2147483647 100
1 3 1 100
2 4 2147483647 10
1 4 1 10
2 4 2147483647 10
1 4 1 10
2 8 3 0
3 5 2147483647 100
1 5 1 100
3 8 1 0
3 2 2147483647 0
4 5 2147483647 10
1 5 1 10
4 8 1 0
4 2 2147483647 0
5 6 2147483647 1
1 6 1 1
5 6 2147483647 1
1 6 1 1
5 7 2147483647 1
1 7 1 1
5 8 3 0
5 2 2147483647 ...

output:


result:


Test #2:

score: 0
Runtime Error

input:

12 49
2 10 2147483647 5
1 10 1 5
2 5 2147483647 50
1 5 1 50
2 9 2147483647 8
1 9 1 8
2 8 2147483647 47
1 8 1 47
2 11 2147483647 17
1 11 1 17
2 12 5 0
3 12 0 0
3 2 2147483647 0
4 6 2147483647 18
1 6 1 18
4 11 2147483647 12
1 11 1 12
4 9 2147483647 14
1 9 1 14
4 12 3 0
4 2 2147483647 0
5 11 2147483647...

output:


result:


Test #3:

score: 0
Runtime Error

input:

27 169
2 15 2147483647 24
1 15 1 24
2 19 2147483647 96
1 19 1 96
2 12 2147483647 49
1 12 1 49
2 13 2147483647 75
1 13 1 75
2 24 2147483647 2
1 24 1 2
2 27 5 0
3 27 0 0
3 2 2147483647 0
4 11 2147483647 99
1 11 1 99
4 3 2147483647 85
1 3 1 85
4 27 2 0
4 2 2147483647 0
5 27 0 0
5 2 2147483647 0
6 9 214...

output:


result:


Test #4:

score: 0
Runtime Error

input:

77 2149
2 42 2147483647 33
1 42 1 33
2 68 2147483647 30
1 68 1 30
2 76 2147483647 13
1 76 1 13
2 51 2147483647 93
1 51 1 93
2 12 2147483647 39
1 12 1 39
2 57 2147483647 74
1 57 1 74
2 70 2147483647 21
1 70 1 21
2 73 2147483647 24
1 73 1 24
2 52 2147483647 54
1 52 1 54
2 15 2147483647 99
1 15 1 99
2 ...

output:


result:


Test #5:

score: 0
Runtime Error

input:

102 4199
2 48 2147483647 42
1 48 1 42
2 85 2147483647 50
1 85 1 50
2 22 2147483647 83
1 22 1 83
2 95 2147483647 97
1 95 1 97
2 82 2147483647 34
1 82 1 34
2 25 2147483647 72
1 25 1 72
2 4 2147483647 17
1 4 1 17
2 47 2147483647 10
1 47 1 10
2 71 2147483647 12
1 71 1 12
2 68 2147483647 39
1 68 1 39
2 2...

output:


result:


Test #6:

score: 0
Runtime Error

input:

102 4199
2 79 2147483647 13
1 79 1 13
2 83 2147483647 73
1 83 1 73
2 75 2147483647 90
1 75 1 90
2 30 2147483647 92
1 30 1 92
2 54 2147483647 25
1 54 1 25
2 66 2147483647 53
1 66 1 53
2 52 2147483647 37
1 52 1 37
2 63 2147483647 46
1 63 1 46
2 11 2147483647 20
1 11 1 20
2 55 2147483647 53
1 55 1 53
2...

output:


result:


Test #7:

score: 0
Runtime Error

input:

102 4199
2 39 2147483647 45
1 39 1 45
2 51 2147483647 11
1 51 1 11
2 86 2147483647 63
1 86 1 63
2 23 2147483647 46
1 23 1 46
2 48 2147483647 63
1 48 1 63
2 87 2147483647 8
1 87 1 8
2 73 2147483647 63
1 73 1 63
2 5 2147483647 52
1 5 1 52
2 80 2147483647 21
1 80 1 21
2 31 2147483647 44
1 31 1 44
2 101...

output:


result:


Test #8:

score: 0
Runtime Error

input:

302 10599
2 72 2147483647 169
1 72 1 169
2 260 2147483647 165
1 260 1 165
2 12 2147483647 108
1 12 1 108
2 16 2147483647 26
1 16 1 26
2 28 2147483647 148
1 28 1 148
2 7 2147483647 74
1 7 1 74
2 139 2147483647 199
1 139 1 199
2 231 2147483647 9
1 231 1 9
2 287 2147483647 123
1 287 1 123
2 135 2147483...

output:


result:


Test #9:

score: 0
Runtime Error

input:

302 10599
2 222 2147483647 132
1 222 1 132
2 17 2147483647 7
1 17 1 7
2 177 2147483647 253
1 177 1 253
2 90 2147483647 195
1 90 1 195
2 128 2147483647 289
1 128 1 289
2 42 2147483647 193
1 42 1 193
2 213 2147483647 133
1 213 1 133
2 263 2147483647 293
1 263 1 293
2 50 2147483647 155
1 50 1 155
2 228...

output:


result:


Test #10:

score: 0
Runtime Error

input:

302 10599
2 176 2147483647 289
1 176 1 289
2 190 2147483647 99
1 190 1 99
2 10 2147483647 96
1 10 1 96
2 240 2147483647 165
1 240 1 165
2 273 2147483647 205
1 273 1 205
2 248 2147483647 194
1 248 1 194
2 220 2147483647 122
1 220 1 122
2 194 2147483647 167
1 194 1 167
2 8 2147483647 67
1 8 1 67
2 227...

output:


result: