本文主要是介绍hdu contest day1 1007 Tricks Device，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：http://acm.hdu.edu.cn/contests/contest_showproblem.php?cid=589&pid=1007
思路：预处理出最短路，跑最小割
lll的代码：
#include<bits/stdc++.h>
#define maxn 2100
#define maxm 180000
#define inf 0x7fffffff
#define min(a,b) ((a)>(b)?(b):(a))
using namespace std;
int pre[maxm],now[maxn],son[maxm],tot,val[maxm],st[maxm],n,m;
void con(int a,int b,int c){pre[++tot]=now[a];now[a]=tot;son[tot]=b;val[tot]=c;st[tot]=a;
}
int pre1[maxm],now1[maxn],son1[maxm],tot1,cap[maxm],opp[maxm],line[maxm<<1];
void con1(int a,int b,int c){pre1[++tot1]=now1[a];now1[a]=tot1;son1[tot1]=b;cap[tot1]=c;
}
void doit(int a,int b,int c){con1(a,b,c);con1(b,a,0);opp[tot-1]=tot;opp[tot]=tot-1;
}
int ans,dis[maxn],dep[maxn];bool bb[maxn];
void spfa(){int head=0,tail=1;memset(dis,63,sizeof(dis));memset(dep,-1,sizeof(dep));memset(bb,0,sizeof(bb));dis[1]=0;line[1]=1;dep[1]=0;do{int x=line[++head];bb[x]=0;for(int p=now[x];p;p=pre[p])if(dis[x]+val[p]<dis[son[p]]){dep[son[p]]=dep[x]+1;dis[son[p]]=dis[x]+val[p];if(!bb[son[p]]){bb[son[p]]=true;line[++tail]=son[p];}}else if(dis[x]+val[p]==dis[son[p]]&&dep[son[p]]>dep[x]+1)dep[son[p]]=dep[x]+1;}while(head!=tail);for(int i=1;i<=tot;i++)if(dis[st[i]]+val[i]==dis[son[i]])doit(st[i],son[i],1);ans=m-dep[n];
}
bool bfs(){int head=0,tail=1;memset(dep,-1,sizeof(dep));dep[1]=0;line[1]=1;do{int x=line[++head];for(int p=now1[x];p;p=pre1[p])if(cap[p]&&dep[son1[p]]==-1){dep[son1[p]]=dep[x]+1;if(son1[p]==n)return true;line[++tail]=son1[p];}}while(head!=tail);return false;
}
int dfs(int x,int flow){if(x==n)return flow;int ans=0,p;for(p=now1[x];p;p=pre1[p])if(dep[son1[p]]==dep[x]+1&&cap[p]){int t=dfs(son1[p],min(flow,cap[p]));flow-=t;cap[p]-=t;cap[opp[p]]+=t;ans+=t;if(!flow)break;}if(!p)dep[x]=-1;return ans;
}
int mflow(){int ans=0;while(bfs())ans+=dfs(1,inf);return ans;
}
void work(){tot=tot1=0;memset(now,0,sizeof(now));memset(now1,0,sizeof(now1));for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);con(a,b,c);con(b,a,c);}spfa();printf("%d %d\n",mflow(),ans);
}
int main(){while(scanf("%d%d",&n,&m)!=EOF)work();return 0;
}这篇关于hdu contest day1 1007 Tricks Device的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
