C++(g++ 7.5.0) 解法, 执行用时: 48ms, 内存消耗: 5848K, 提交时间: 2022-11-20 13:32:12

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
vector<vector<int>> adj(N);
int indeg[N],f[N],a[N],b[N],root[N],tot;
int dfs(int cur,int par)
{
    int ans = 0x7f7f7f7f;
    f[cur] = b[cur] - a[cur] + max(f[par] - b[cur],0);
    ans = min(f[cur],ans);
    for(int u : adj[cur])
        ans = min( dfs(u,cur),ans );
    return ans;

}
void solve()
{
    int n,m,sum = 0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d %d",a + i,b + i);
    for(int i=0;i<n-m;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        adj[v].push_back(u);
        indeg[u]++;
    }
    for(int i=1;i<=n;i++)
        if (!indeg[i])
            root[++tot] = i;
    for(int i = 1;i<=tot;i++)
        sum += dfs(root[i],0);
    printf("%d\n",sum);
}

int main()
{
    solve();
}

Python3 解法, 执行用时: 733ms, 内存消耗: 46828K, 提交时间: 2022-06-20 10:00:42

n,m=map(int,input().split())
team=[]
road={}
a=set()
b=set(x for x in range(n))
for _ in range(n):
    team.append([int(x) for x in input().split()])
for _ in range(n-m):
    x ,y =[int(x)-1 for x in input().split()]
    if y not in road:
        road[y] = [x]
    else:
        road[y].append(x)
    a.add(x) #左边都是非决战区
varea = list(b-a)  #决战区
soldier=0
res=[0]
def dfs(x,y): #节点，到达该节点需要多少人
    y = max(y,team[x][1]) - team[x][0]
    res[0] =  min(y,res[0])
    if x not in road:
        return
    for r in road[x]:
        dfs(r,y)
    return
for x in varea:
    res[0] = team[x][1] -  team[x][0]
    tmp = res[0]
    dfs(x,tmp)
    soldier  = soldier + res[0]
print(soldier)

C++ 解法, 执行用时: 104ms, 内存消耗: 5624K, 提交时间: 2021-11-23 15:00:26

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],b[N],f[N],in[N];
vector<int> g[N];
int n,m;
int ans , res ;
void dfs(int u,int need){
	f[u] = max(f[u],f[u]+need-b[u]);
	res = min(res,f[u]);
	for(auto v : g[u]){
		//vis[v]=1;
		dfs(v,f[u]);
	}
}
int main() {
	cin >> n >> m;
	for(int i=1; i<=n; i++) {
		cin >> a[i] >> b[i];
		f[i]= b[i]-a[i];
	}
	for(int i=1;i<=n-m;i++){
		int u,v;
		cin >> u >> v;
		g[v].push_back(u);
		in[u]++;
	}
	for(int i=1;i<=n;i++){
		if(!in[i]){
			//vis[i]=1;
			res = 0x3f3f3f3f;
			dfs(i,0);
			ans+=res;
		}
	}
	cout << ans << endl;
	return 0;
}