#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
int n,m,s,t;
int a[100001];
int b[100001];
ll c[100001];
ll eq[200001];
ll d[200003];
bool vis[200003],inq[200003];
ll cp[1000001],wt[1000001];
vector<pair<int,int> >adj[200003];
int sz;
bool fuck[100001];
void init(){
for(int i=1; i<=t ;i++) adj[i].clear();
sz=0;
}
void addedge(int u,int v,ll cap,ll wei){
cp[sz]=cap;cp[sz^1]=0;
wt[sz]=wei;wt[sz^1]=-wei;
adj[u].pb({v,sz});
adj[v].pb({u,sz^1});
sz+=2;
}
ll dfs(int id,ll f){
if(id==t) return f;
if(vis[id]) return 0;
vis[id]=true;
ll res=0;
for(auto cur:adj[id]){
if(d[cur.fi]==d[id]+wt[cur.se] && cp[cur.se]>0){
ll tmp=dfs(cur.fi,min(f,cp[cur.se]));
if(tmp){
cp[cur.se]-=tmp;
cp[cur.se^1]+=tmp;
return tmp;
}
}
}
return 0;
}
ll flow(){
if(n>3000) return 0;
ll res=0;//min cost
while(true){
for(int i=1; i<=t ;i++){
d[i]=1e18;
inq[i]=false;
}
queue<int>q;
d[s]=0;
inq[s]=true;
q.push(s);
while(!q.empty()){
int cur=q.front();
q.pop();
inq[cur]=false;
for(auto newi:adj[cur]){
if(d[newi.fi]>d[cur]+wt[newi.se] && cp[newi.se]>0){
d[newi.fi]=d[cur]+wt[newi.se];
if(!inq[newi.fi]){
inq[newi.fi]=true;
q.push(newi.fi);
}
}
}
}
if(d[t]==1e18) return res;
while(true){
for(int j=1; j<=t ;j++) vis[j]=false;
ll tmp=dfs(s,1e18);
if(tmp==0) break;
res+=tmp*d[t];
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
s=n+1,t=n+2;
for(int i=1; i<=m ;i++){
cin >> a[i] >> b[i] >> c[i];
if(a[i]==b[i]){
fuck[i]=true;
continue;
}
if(a[i]>b[i]) swap(a[i],b[i]);
b[i]--;
if(a[i]==1){
eq[n]-=c[i];
eq[b[i]]+=c[i];
}
else{
eq[a[i]-1]+=c[i];
eq[b[i]]-=c[i];
}
}
ll ans=1e18;
for(int i=0; i<2 ;i++){
init();
bool odd=i;
for(int j=1; j<=n ;j++){
ll cur=eq[j]-odd;
odd=false;
if(cur&1){
cur++;
odd=true;
}
if(cur>0) addedge(s,j,cur/2,0);
else addedge(j,t,-cur/2,0);
if(j==1) addedge(1,n,1e18,2);
else addedge(j,j-1,1e18,0);
}
for(int j=1; j<=m ;j++){
if(fuck[j]) continue;
if(a[j]==1) addedge(b[j],n,c[j],1);
else addedge(a[j]-1,b[j],c[j],1);
}
ans=min(ans,flow()+i);
}
cout << ans << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5168 KB |
Output is correct |
4 |
Correct |
6 ms |
5196 KB |
Output is correct |
5 |
Correct |
8 ms |
5240 KB |
Output is correct |
6 |
Correct |
7 ms |
5292 KB |
Output is correct |
7 |
Correct |
6 ms |
5296 KB |
Output is correct |
8 |
Correct |
7 ms |
5296 KB |
Output is correct |
9 |
Correct |
6 ms |
5332 KB |
Output is correct |
10 |
Correct |
7 ms |
5332 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
6 ms |
5424 KB |
Output is correct |
13 |
Correct |
7 ms |
5424 KB |
Output is correct |
14 |
Correct |
7 ms |
5424 KB |
Output is correct |
15 |
Correct |
7 ms |
5424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5168 KB |
Output is correct |
4 |
Correct |
6 ms |
5196 KB |
Output is correct |
5 |
Correct |
8 ms |
5240 KB |
Output is correct |
6 |
Correct |
7 ms |
5292 KB |
Output is correct |
7 |
Correct |
6 ms |
5296 KB |
Output is correct |
8 |
Correct |
7 ms |
5296 KB |
Output is correct |
9 |
Correct |
6 ms |
5332 KB |
Output is correct |
10 |
Correct |
7 ms |
5332 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
6 ms |
5424 KB |
Output is correct |
13 |
Correct |
7 ms |
5424 KB |
Output is correct |
14 |
Correct |
7 ms |
5424 KB |
Output is correct |
15 |
Correct |
7 ms |
5424 KB |
Output is correct |
16 |
Correct |
8 ms |
5484 KB |
Output is correct |
17 |
Correct |
11 ms |
5484 KB |
Output is correct |
18 |
Correct |
10 ms |
5484 KB |
Output is correct |
19 |
Correct |
9 ms |
5484 KB |
Output is correct |
20 |
Correct |
10 ms |
5484 KB |
Output is correct |
21 |
Correct |
9 ms |
5484 KB |
Output is correct |
22 |
Correct |
11 ms |
5484 KB |
Output is correct |
23 |
Correct |
9 ms |
5484 KB |
Output is correct |
24 |
Correct |
10 ms |
5484 KB |
Output is correct |
25 |
Correct |
9 ms |
5484 KB |
Output is correct |
26 |
Correct |
9 ms |
5484 KB |
Output is correct |
27 |
Correct |
8 ms |
5484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5168 KB |
Output is correct |
4 |
Correct |
6 ms |
5196 KB |
Output is correct |
5 |
Correct |
8 ms |
5240 KB |
Output is correct |
6 |
Correct |
7 ms |
5292 KB |
Output is correct |
7 |
Correct |
6 ms |
5296 KB |
Output is correct |
8 |
Correct |
7 ms |
5296 KB |
Output is correct |
9 |
Correct |
6 ms |
5332 KB |
Output is correct |
10 |
Correct |
7 ms |
5332 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
6 ms |
5424 KB |
Output is correct |
13 |
Correct |
7 ms |
5424 KB |
Output is correct |
14 |
Correct |
7 ms |
5424 KB |
Output is correct |
15 |
Correct |
7 ms |
5424 KB |
Output is correct |
16 |
Correct |
8 ms |
5484 KB |
Output is correct |
17 |
Correct |
11 ms |
5484 KB |
Output is correct |
18 |
Correct |
10 ms |
5484 KB |
Output is correct |
19 |
Correct |
9 ms |
5484 KB |
Output is correct |
20 |
Correct |
10 ms |
5484 KB |
Output is correct |
21 |
Correct |
9 ms |
5484 KB |
Output is correct |
22 |
Correct |
11 ms |
5484 KB |
Output is correct |
23 |
Correct |
9 ms |
5484 KB |
Output is correct |
24 |
Correct |
10 ms |
5484 KB |
Output is correct |
25 |
Correct |
9 ms |
5484 KB |
Output is correct |
26 |
Correct |
9 ms |
5484 KB |
Output is correct |
27 |
Correct |
8 ms |
5484 KB |
Output is correct |
28 |
Correct |
119 ms |
6164 KB |
Output is correct |
29 |
Correct |
144 ms |
6164 KB |
Output is correct |
30 |
Correct |
114 ms |
6164 KB |
Output is correct |
31 |
Correct |
183 ms |
6164 KB |
Output is correct |
32 |
Correct |
107 ms |
6164 KB |
Output is correct |
33 |
Correct |
135 ms |
6228 KB |
Output is correct |
34 |
Correct |
141 ms |
6228 KB |
Output is correct |
35 |
Correct |
104 ms |
6228 KB |
Output is correct |
36 |
Correct |
137 ms |
6228 KB |
Output is correct |
37 |
Correct |
179 ms |
6428 KB |
Output is correct |
38 |
Correct |
13 ms |
6428 KB |
Output is correct |
39 |
Correct |
40 ms |
6428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5168 KB |
Output is correct |
4 |
Correct |
6 ms |
5196 KB |
Output is correct |
5 |
Correct |
8 ms |
5240 KB |
Output is correct |
6 |
Correct |
7 ms |
5292 KB |
Output is correct |
7 |
Correct |
6 ms |
5296 KB |
Output is correct |
8 |
Correct |
7 ms |
5296 KB |
Output is correct |
9 |
Correct |
6 ms |
5332 KB |
Output is correct |
10 |
Correct |
7 ms |
5332 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
6 ms |
5424 KB |
Output is correct |
13 |
Correct |
7 ms |
5424 KB |
Output is correct |
14 |
Correct |
7 ms |
5424 KB |
Output is correct |
15 |
Correct |
7 ms |
5424 KB |
Output is correct |
16 |
Correct |
8 ms |
5484 KB |
Output is correct |
17 |
Correct |
11 ms |
5484 KB |
Output is correct |
18 |
Correct |
10 ms |
5484 KB |
Output is correct |
19 |
Correct |
9 ms |
5484 KB |
Output is correct |
20 |
Correct |
10 ms |
5484 KB |
Output is correct |
21 |
Correct |
9 ms |
5484 KB |
Output is correct |
22 |
Correct |
11 ms |
5484 KB |
Output is correct |
23 |
Correct |
9 ms |
5484 KB |
Output is correct |
24 |
Correct |
10 ms |
5484 KB |
Output is correct |
25 |
Correct |
9 ms |
5484 KB |
Output is correct |
26 |
Correct |
9 ms |
5484 KB |
Output is correct |
27 |
Correct |
8 ms |
5484 KB |
Output is correct |
28 |
Correct |
119 ms |
6164 KB |
Output is correct |
29 |
Correct |
144 ms |
6164 KB |
Output is correct |
30 |
Correct |
114 ms |
6164 KB |
Output is correct |
31 |
Correct |
183 ms |
6164 KB |
Output is correct |
32 |
Correct |
107 ms |
6164 KB |
Output is correct |
33 |
Correct |
135 ms |
6228 KB |
Output is correct |
34 |
Correct |
141 ms |
6228 KB |
Output is correct |
35 |
Correct |
104 ms |
6228 KB |
Output is correct |
36 |
Correct |
137 ms |
6228 KB |
Output is correct |
37 |
Correct |
179 ms |
6428 KB |
Output is correct |
38 |
Correct |
13 ms |
6428 KB |
Output is correct |
39 |
Correct |
40 ms |
6428 KB |
Output is correct |
40 |
Incorrect |
294 ms |
38372 KB |
Output isn't correct |
41 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5168 KB |
Output is correct |
4 |
Correct |
6 ms |
5196 KB |
Output is correct |
5 |
Correct |
8 ms |
5240 KB |
Output is correct |
6 |
Correct |
7 ms |
5292 KB |
Output is correct |
7 |
Correct |
6 ms |
5296 KB |
Output is correct |
8 |
Correct |
7 ms |
5296 KB |
Output is correct |
9 |
Correct |
6 ms |
5332 KB |
Output is correct |
10 |
Correct |
7 ms |
5332 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
6 ms |
5424 KB |
Output is correct |
13 |
Correct |
7 ms |
5424 KB |
Output is correct |
14 |
Correct |
7 ms |
5424 KB |
Output is correct |
15 |
Correct |
7 ms |
5424 KB |
Output is correct |
16 |
Correct |
8 ms |
5484 KB |
Output is correct |
17 |
Correct |
11 ms |
5484 KB |
Output is correct |
18 |
Correct |
10 ms |
5484 KB |
Output is correct |
19 |
Correct |
9 ms |
5484 KB |
Output is correct |
20 |
Correct |
10 ms |
5484 KB |
Output is correct |
21 |
Correct |
9 ms |
5484 KB |
Output is correct |
22 |
Correct |
11 ms |
5484 KB |
Output is correct |
23 |
Correct |
9 ms |
5484 KB |
Output is correct |
24 |
Correct |
10 ms |
5484 KB |
Output is correct |
25 |
Correct |
9 ms |
5484 KB |
Output is correct |
26 |
Correct |
9 ms |
5484 KB |
Output is correct |
27 |
Correct |
8 ms |
5484 KB |
Output is correct |
28 |
Correct |
119 ms |
6164 KB |
Output is correct |
29 |
Correct |
144 ms |
6164 KB |
Output is correct |
30 |
Correct |
114 ms |
6164 KB |
Output is correct |
31 |
Correct |
183 ms |
6164 KB |
Output is correct |
32 |
Correct |
107 ms |
6164 KB |
Output is correct |
33 |
Correct |
135 ms |
6228 KB |
Output is correct |
34 |
Correct |
141 ms |
6228 KB |
Output is correct |
35 |
Correct |
104 ms |
6228 KB |
Output is correct |
36 |
Correct |
137 ms |
6228 KB |
Output is correct |
37 |
Correct |
179 ms |
6428 KB |
Output is correct |
38 |
Correct |
13 ms |
6428 KB |
Output is correct |
39 |
Correct |
40 ms |
6428 KB |
Output is correct |
40 |
Incorrect |
294 ms |
38372 KB |
Output isn't correct |
41 |
Halted |
0 ms |
0 KB |
- |