| HDNOIP201304阻断传染 |
| 难度级别： A； 编程语言：不限；运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
H国有n个城市,n个城市用n-1条双向道路相互连通构成一棵树,1号城市是首都，也是树中的根节点。H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市)，决定在一些公路上设检疫关卡，但在不同道路上设卡的代价可能不同，为了防止边境城市受传染，必需让从首都到每个边境城市的路径上都至少有一个检疫关卡，请你编程求能阻止传染的最小设卡总代价。 |
输入 |
第一行一个整数 n,表示城市个数。 接下来的 n-1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市u到城市v有一条双向道路，设卡代价为w。 数据保证输入的是一棵树,且根节点编号为1。 |
输出 |
其中共一行,包含一个整数,表示控制疫情所需要的最少设卡总代价。 |
输入示例 |
9 2 1 888 1 3 88 2 4 6 5 2 8 6 3 100 3 7 10 8 3 50 7 9 1 |
输出示例 |
102 |
其他说明 |
对于 60%的数据,2<n<10，对于 80%的数据,2<n<100，对于 100%的数据,2<n<100000 |
题解：直接写个最小割跑去吧。。。
Wa了两发是因为bfs得时候忘设vis[S]=true了。。。QAQ。。。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxm=+,inf=-1u>>;
int out[maxn];
struct isap{
struct ted{int x,y,w;ted*nxt,*re;}adj[maxm],*fch[maxn],*ms,*cur[maxn],*ret[maxn];
int d[maxn],gap[maxn],n,S,T;
void init(int n){this->n=n;memset(d,-,sizeof(d));ms=adj;return;}
void add(int x,int y,int w){
*ms=(ted){x,y,w,fch[x],ms+};fch[x]=ms++;
*ms=(ted){y,x,,fch[y],ms-};fch[y]=ms++;
return;
}
void bfs(){
queue<int>Q;Q.push(T);d[T]=;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(ted*e=fch[u];e;e=e->nxt){
int v=e->y;if(d[v]<)d[v]=d[u]+,Q.push(v);
}
} return;
}
int mxflow(int S,int T){
this->S=S;this->T=T;bfs();ted*e;int k=S,flow=;
for(int i=;i<=n;i++)gap[d[i]]++,cur[i]=fch[i];
while(d[S]<n){
if(k==T){
int mi=inf,pos;for(int i=S;i!=T;i=cur[i]->y)if(cur[i]->w<mi)mi=cur[i]->w,pos=i;
for(int i=S;i!=T;i=cur[i]->y)cur[i]->w-=mi,cur[i]->re->w+=mi;flow+=mi;k=pos;
} for(e=cur[k];e;e=e->nxt)if(e->w&&d[k]==d[e->y]+)break;
if(e)cur[k]=e,ret[e->y]=e->re,k=e->y;
else{if(--gap[d[k]]==)break;cur[k]=fch[k];int mi=n;
for(e=fch[k];e;e=e->nxt)if(e->w&&d[e->y]<mi)mi=d[e->y];
d[k]=mi+;gap[d[k]]++;if(k!=S)k=ret[k]->y;
}
} return flow;
}
}sol;
struct ted{int x,y,w;ted*nxt;}adj[maxm],*fch[maxn],*ms=adj;
void add(int x,int y,int w){
*ms=(ted){x,y,w,fch[x]};fch[x]=ms++;
*ms=(ted){y,x,w,fch[y]};fch[y]=ms++;
return;
}
bool vis[maxn];
void bfs(int S){
queue<int>Q;Q.push(S);vis[S]=true;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(ted*e=fch[u];e;e=e->nxt){
int v=e->y;if(!vis[v]){
vis[v]=true;out[u]++;sol.add(u,v,e->w);Q.push(v);//printf("add:%d->%d %d\n",u,v,e->w);system("pause");
}
}
} return;
}
int n,m;queue<int>tset;
void makeG(){
for(int i=;i<=n;i++)if(!out[i])tset.push(i);//printf("tset:");
while(!tset.empty()){
int x=tset.front();tset.pop();sol.add(x,n+,1e9);//printf("%d ",x);
} return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
void init(){
n=read();m=~-n;sol.init(n+);int x,y,w;
for(int i=;i<=m;i++){
x=read();y=read();w=read();add(x,y,w);
}bfs();makeG();write(sol.mxflow(,n+));
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}