南外Day11

A&B&C&D&E

水
注意D的细节，E的距离计算方式

F

容易得到这是个基环森林（雾
环周围可以拓扑排序，环内算出来后取最小值

#include<bits/stdc++.h>
#define GP pair<int,int>
#define MP make_pair
#define MX 200005
using namespace std;
GP m[MX];vector<int> v[MX],col[MX];
int n,ans,cnt,a,b,sy[MX],q[MX],rd[MX],sr[MX],pk[MX],qz[MX],pd[MX];
void dfs(int t,int id){
    sy[t]=id;
    col[id].push_back(t);
    for(auto u:v[t]){
        if(sy[u]) continue;
        dfs(u,id);
    }
}
int top(int id){
    int l=1,r=0,cp=0,res=0;//rd[n+1]=1;sr[n+1]=0;
    for(auto u:col[id]){
        int ed=1;//+(ts==u);
        if(v[u].size()<=ed)
            q[++r]=u;
        rd[u]=v[u].size()-ed;
        sr[u]=pk[u]=0;
    }
    while(l<=r){
        int tp=q[l];l++;cp++;pk[tp]=1;
        res+=max(0,m[tp].second-sr[tp]);
        sr[m[tp].first]+=m[tp].second;
        rd[m[tp].first]--;
        if(!rd[m[tp].first])
            q[++r]=m[tp].first;
    }
    return res;
}
int solve(int id){
    int fst=top(id);int st=0,ls,res=1000000000;
    for(auto u:col[id]){
        if(pk[u]) continue;
        st=u;break;
    }
    if(!st){cout<<"?";exit(0);}
    int r=0;
    ls=st;do{
        r++;q[r]=q[r-1]+max(0,m[st].second-qz[st]);
        pd[m[st].first]=m[st].second;
        st=m[st].first;
    }while(st!=ls);
    int l=0;
    ls=st;do{
        l++;
        q[l+r]=q[r]-q[l]+q[l-1];
        st=m[st].first;
    }while(st!=ls);
    l=r;ls=st;do{
        l++;
        res=min(res,q[l]+max(0,m[st].second-qz[st]+pd[st]));
        st=m[st].first;
    }while(st!=ls);
    return fst+res;
}
signed main(){
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a>>b;qz[a]+=b;
        m[i]=MP(a,b);
        v[i].push_back(a);
        v[a].push_back(i);
    }
    for(int i=1;i<=n;i++){
        if(!sy[i]){
            cnt++;
            dfs(i,cnt);
        }
    }
    for(int i=1;i<=cnt;i++)
        ans+=solve(i);
    cout<<ans;
    return 0;
}

G&H

orz
G欧拉路径，H是2-SAT
但是不会写