Submission #55848640

---

Source Code Expand

// LUOGU_RID: 167598410
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int N=2e5+5,inf=0x3f3f3f3f3f3f3f3f;    
struct node{int x,v,id;};
vector<node> v[N];
int sum;
void add(int x,int y,int val){
    int sti=v[x].size(),edi=v[y].size();
    if(val<0){
        sum-=val;
        return;
    }
    v[x].push_back({y,val,edi});
    v[y].push_back({x,0,sti});
}
int n,m,s,t,dep[N],p[N];
bool bfs(){
    queue<int> q;
    memset(dep,-1,sizeof(dep));
    memset(p,0,sizeof(p));
    q.push(s),dep[s]=0;
    while(!q.empty()){
        int top=q.front();q.pop();
        for(node i:v[top]){
            if(dep[i.x]==-1&&i.v){
                dep[i.x]=dep[top]+1;
                q.push(i.x);
            }
        }
    }
    return dep[t]!=-1;
}
int dfs(int x,int flow){
    int tmp=flow;
    if(x==t||!flow){
        return flow;
    }
    for(int id=p[x];id<v[x].size();id++){
        p[x]=id;
        node &i=v[x][id];
        if(dep[x]+1==dep[i.x]&&i.v>0){
            int t=dfs(i.x,min(i.v,tmp));
			if(!t){
                dep[i.x]=-1;
            }
			else{
                i.v-=t;
                v[i.x][i.id].v+=t;
                tmp-=t;
            }
        }

    }
    return flow-tmp;
}
int dinic(){
    int ans=0;
    while(bfs()){
        ans+=dfs(s,inf);
    }
    return ans;
}
int a[N],b[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m,t=N-1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        add(s,i,a[i]+b[i]);
        add(i+n,t,a[i]-b[i]);
        add(i,i+n,inf);
    }
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        add(x,y+n,inf);
        add(y,x+n,inf);
    }
    cout<<sum-dinic()<<'\n';
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘long long int dfs(long long int, long long int)’:
Main.cpp:43:23: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<node>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   43 |     for(int id=p[x];id<v[x].size();id++){
      |                     ~~^~~~~~~~~~~~

Judge Result