传送门

洛谷


题目描述

冴月麟为了守护幻想乡,而制造了幻想乡的倒影,将真实的幻想乡封印了。任何人都无法进入真实的幻想乡了,但是她给前来救她的魏潇承留了一个线索。

她设置了一棵树(有根)。树的每一条边上具有割掉该边的代价。

魏潇承需要计算出割开这棵树的最小代价,这就是冴月麟和魏潇承约定的小秘密。

帮帮魏潇承吧。

注:所谓割开一棵有根树,就是删除若干条边,使得任何任何叶子节点和根节点不连通。


输入输出格式

输入格式:

输入第一行两个整数nS表示树的节点个数和根。

接下来n-1行每行三个整数abc,表示ab之间有一条代价为c的边。

输出格式:

输出包含一行,一个整数,表示所求最小代价。


输入输出样例

输入样例#1:

4 1
1 2 1
1 3 1
1 4 1

输出样例#1:

3

输入样例#2:

4 1
1 2 3
2 3 1
3 4 2

输出样例#2:

1

说明

对于20 \%的数据,n \le 10

对于50 \%的数据,n \le 1000

对于100 \%的数据,n \le 100000


解题思路:

最小割问题,用最大流解决。网络流裸题。

Code:

/*Program from Luvwgyx*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int inf=1e9;
const int maxn=2e5+10;
queue<ll >q;
struct node{int to,nxt;ll w;}e[maxn<<3];
int n,S,T,tot=1,head[maxn],d[maxn],f[maxn];ll maxflow;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(ll x){print(x);puts("");}
void add(int u,int v,int w){e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;}
bool bfs(){
    memset(d,0,sizeof(d));
    while(!q.empty())q.pop();
    q.push(S);d[S]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
            if(e[i].w&&!d[v]){
                q.push(v);d[v]=d[x]+1;
                if(v==T)return 1;
            }
    }return 0;
}
ll dinic(int x,ll flow){
    if(x==T)return flow;
    ll rest=flow,w;
    for(int i=head[x],v=e[i].to;i&&rest;i=e[i].nxt,v=e[i].to)
        if(e[i].w&&d[v]==d[x]+1){
            w=dinic(v,min(rest,e[i].w));
            if(!w)d[v]=0;
            e[i].w-=w;e[i^1].w+=w;rest-=w;
        }
    return flow-rest;
}
int main(){
    n=read();S=read();T=n+1;
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,w);f[u]++;f[v]++;
    }for(int i=1;i<=n;i++)if(f[i]==1&&i!=S)add(T,i,inf),add(i,T,inf);
    while(bfs())maxflow+=dinic(S,inf);
    write(maxflow);
    return 0;
}