Vsinger_洛天依 @ 2024-09-04 21:16:02
感觉写的挺对的,但是只有20分
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define int long long
#define ull unsigned long long
#define re register
#define for_(a,b,P) for(int a=b;a<=P;a++)
#define _for(a,b,P) for(int a=b;a>=P;a--)
#define firein(a) freopen(a".in","r",stdin)
#define fireout(a) freopen(a".out","W",stdout)
#define fire(a) (firein(a),fireout(a))
#define lc(q) (q<<1)
#define rc(q) (q<<1|1)
#define mid(l,r) ((l+r)>>1)
using namespace std;
namespace IO{
inline int read(){
char ch=getchar();
int s=0,f=1;
while(ch<'0'||'9'<ch) {
if(ch == '-'){
f = -1;
}
ch = getchar();
}
while('0'<ch&&ch<'9'){
s = s*10 + ch - '0';
ch = getchar();
}
return s * f;
}
inline void write(int x){
if(x < 0){
putchar('-');
x *= -1;
}
write(x/10);
putchar(x%10 + '0');
}
inline void print(int x,char s){
write(x);
putchar(s);
}
inline double rnd(){
char P = getchar();
int f = 1,s = 0,x = 0;
double t = 0;
while((P<'0'||P>'9')&&P!='.'){
if(P == '-')
f *= -1;
P = getchar();
}
while(P>='0'&&P<='9'&&P!='.'){
x = x*10 + (P^48);
P = getchar();
}
if(P=='.'){
P=getchar();
}
else{
return x*f;
}
while(P>='0'&&P<='9'){
s+=1;
t=t*10+(P^48);
P=getchar();
}
while(s--){
t/=10.0;
x=(x+t)*f;
}
return x;
}
}
using namespace IO;
const int N = 1000005;
const int M = 10000005;
const ll INF=0x66ccff0712ll;
const ll inf=LLONG_MAX;
int Head[N],ver[N],Edge[N],nxt[N],d[N];
int now[N],tot,n,m,s,t,maxflow,flow;
inline void Add(int x,int y,int z){
ver[++tot] = y;
Edge[tot] = z;
nxt[tot] = Head[x];
Head[x] = tot;
}
queue<int> q;
inline bool BFS(){
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
q.push(s);
d[s] = 1; now[s] = Head[s];
while(q.size()){
int x = q.front(); q.pop();
for(int i=Head[x] ; i ; i=nxt[i]){
if(Edge[i] && !d[ver[i]]){
q.push(ver[i]);
now[ver[i]] = Head[ver[i]];
d[ver[i]] = d[x] + 1;
if(ver[i] == t) return 1;
}
}
}
return 0;
}
inline int Dinic(int x,int f){
if(x==t) return f;
int rest = f;
for(int i = now[x];i && rest;i = nxt[i]){
now [x] = i;
if(Edge[i] && d[ver[i]] == d[x] + 1){
int k = Dinic(ver[i],min(rest,Edge[i]));
if(!k) d[ver[i]] = 0;
Edge[i] -= k;
Edge[i^1] += k;
rest -= k;
}
}
return f - rest;
}
inline void In(){
cin >> n >> m >> s >> t;
tot = 1;
for_(i,1,m){
int x,y,z;
cin >> x >> y >> z;
Add(x,y,z);
Add(y,x,z);
}
while(BFS())
while(flow=Dinic(s,inf))
maxflow += flow;
cout << maxflow << endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
In();
}
by Vsinger_洛天依 @ 2024-09-04 21:16:47
input
10 25 3 1
9 3 80
5 10 62
4 2 13
7 2 20
3 10 90
6 10 53
2 3 11
6 3 45
9 5 37
10 9 93
7 8 28
4 5 28
1 2 52
4 5 54
1 2 62
7 4 64
4 3 40
7 3 39
8 2 72
7 5 5
3 6 88
3 2 56
9 2 72
2 1 81
6 7 84
right output
81
by LuoMuxiaoxiao @ 2024-09-04 21:25:11
咋还在写题,不是军训?
by _空白_ @ 2024-09-25 19:01:31
@Vsinger_洛天依 反边初始权值应该是0吧