题解：P3063 [USACO12DEC] Milk Routing S

Clare613 · 2024-08-05 10:46:48 · 题解

建议降黄或橙 or 加强数据

题目大意:

就是让 L+X/C 小就行了。

思路：

最容易想到的是 SPFA ，但因数据较小，所以 DFS 也能过，而我们的 DFS 是来找容量和延迟最小的最大值。

code

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v,w,fj;
};
vector<node> a[505];
int cnt[505],sum,l[505],ctn,minn=1e9;
int n,m,qwe;
bool f[505][505];
void dfs(int sum,int maxn,int now){//dfs
    if(sum+maxn>minn) return ;//剪枝
    if(now==n){
        minn=min(minn,sum+maxn);//求最小值
        return ;
    }
    for(int i=0;i<a[now].size();i++){
        if(f[now][a[now][i].v]) continue;//走过就不能走
        f[now][a[now][i].v]=1;//标记
        dfs(sum+a[now][i].w,max(maxn,a[now][i].fj),a[now][i].v);//转移
        f[now][a[now][i].v]=0;//取消标记
    }
}
int main(){
    cin>>n>>m>>qwe;
    for(int i=1;i<=m;i++){
        int x,y,z,q;
        cin>>x>>y>>z>>q;
        //建边
        a[x].push_back({y,z,floor(qwe/q)});
        a[y].push_back({x,z,floor(qwe/q)});
    }
    dfs(0,0,1);
    cout<<minn;//输出
    return 0;
}