#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;
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(){
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]) swap(a[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(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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
