QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123163 | #602. 最小费用最大流(随机数据) | c20231020# | 0 | 0ms | 0kb | C++23 | 4.1kb | 2023-07-11 20:17:24 | 2023-07-11 20:17:25 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...