首页 > 代码库 > poj 2455 Secret Milking Machine
poj 2455 Secret Milking Machine
【题意】：(半天没懂题目什么意思，诶。。)FJ有N块地，这些地之间有P条双向路，每条路的都有固定的长度l。现在要你找出从第1块地到第n块地的T条不同路
径，每条路径上的路不能与先前的路径重复，问这些路径中的最长路的最小是多少。
【思路】二分判定最长路的最小值，再用小于这个值的边建图跑最大流。建图的话，整张无向图（记得是无向图！ 对一条边正向方向都要添加wa 好久 ）加一个源点和点1 连边容量无穷大，n点和会汇点连边，容量无穷大，最大流是多少能够找到的不同的路径就是多少。
1 #include<iostream> 2 #include<vector> 3 #include<string.h> 4 #include<queue> 5 #include<cstdio> 6 using namespace std; 7 struct E{int from;int to;int c;int f;}; 8 vector <int> g[220]; 9 vector<E> edge; 10 int d[220],vis[220],cur[220],num[220],p[220]; 11 #define INF 10000000 12 13 struct node{int v,w;}; 14 vector<node> mapp[220]; 15 int n,T; 16 17 void add(int from,int to,int c) 18 { 19 E temp1,temp2; 20 temp1.from =from; temp1.to=to; temp1.c=c;temp1.f=0; 21 temp2.from =to; temp2.to=from; temp2.c=0;temp2.f=0; 22 edge.push_back (temp1); 23 edge.push_back (temp2); 24 int m=edge.size (); 25 g[from].push_back (m-2); 26 g[to].push_back (m-1); 27 } 28 29 void bfs(int s,int t) 30 { 31 int i; 32 queue<int > q; 33 q.push (t); 34 d[t]=0; 35 memset(vis,0,sizeof(vis)); 36 vis[t]=1; 37 while(!q.empty ()) 38 { 39 int t=q.front ();q.pop (); 40 for(i=0;i<g[t].size ();i++) 41 { 42 E e;e=edge[g[t][i]]; 43 if(!vis[e.to]) 44 { 45 q.push (e.to); 46 vis[e.to]=1; 47 d[e.to]=d[t]+1; 48 } 49 } 50 } 51 } 52 53 int zg(int s,int t) 54 { 55 int x=t,a=INF; 56 while(x!=s) 57 { 58 //printf("x %d\n",x); 59 E e=edge[p[x]]; 60 if(a>e.c-e.f) 61 a=e.c-e.f; 62 x=e.from; 63 } 64 x=t; 65 while(x!=s) 66 { 67 edge[p[x]].f+=a; 68 edge[p[x]^1].f-=a; 69 x=edge[p[x]].from ; 70 } 71 return a; 72 } 73 74 int maxflow(int s,int t,int n) 75 { 76 int flow=0,i; 77 bfs(s,t); 78 memset(num,0,sizeof(num)); 79 memset(cur,0,sizeof(cur)); 80 for(i=0;i<=t;i++) 81 num[d[i]]++; 82 int x=s; 83 while(d[s]<=n) 84 { 85 if(x==t) 86 { 87 flow+=zg(s,t); 88 x=s; 89 //printf("flow %d\n",flow); 90 } 91 int ok=0; 92 for(i=cur[x];i<g[x].size ();i++) 93 { 94 E e; 95 e=edge[g[x][i]]; 96 if(e.c>e.f&&d[x]==d[e.to]+1) 97 { 98 ok=1; 99 100 p[e.to]=g[x][i];101 102 cur[x]=i;103 x=e.to;//!@#$%^&104 break;105 }106 }107 if(ok==0)108 {109 int m=n;110 for(i=0;i<g[x].size ();i++)111 {112 E e;113 e=edge[g[x][i]];114 if(e.c>e.f&&m>d[e.to])115 m=d[e.to];116 }117 if(--num[d[x]]==0) break;118 num[d[x]=m+1]++;119 cur[x]=0;////!@#$%^^&120 if(x!=s)121 x=edge[p[x]].from ;122 123 }124 }125 return flow;126 }127 128 bool ok(int x)129 {130 edge.clear();131 for(int i=0;i<=n+1;i++)132 g[i].clear();133 add(0,1,INF);134 for(int i=1;i<=n;i++)135 for(int j=0;j<mapp[i].size();j++)136 if(mapp[i][j].w<=x)137 {138 add(i,mapp[i][j].v,1);139 add(mapp[i][j].v,i,1);140 }141 142 add(n,n+1,INF);143 int flow;144 flow=maxflow(0,n+1,n+1);145 // printf("flow %d x %d\n",flow,x);146 if(flow>=T)147 return true;148 return false;149 }150 151 int solve(int maxe)152 {153 int left=0,right=maxe,ans=INF;154 while(left<=right)155 {156 int mid=(left+right)/2;157 if(ok(mid))158 {159 ans=min(ans,mid);160 right=mid-1;161 }162 else left=mid+1;163 }164 return ans;165 }166 167 int main()168 {169 int m,a,b,c;170 while(~scanf("%d%d%d",&n,&m,&T))171 {172 for(int i=0;i<=n;i++)173 mapp[i].clear();174 int maxe=0;175 for(int i=0;i<m;i++)176 {177 scanf("%d%d%d",&a,&b,&c);178 node temp; temp.v=b; temp.w=c;179 mapp[a].push_back(temp);180 maxe=max(maxe,c);181 }182 printf("%d\n",solve(maxe));183 }184 return 0;185 }
poj 2455 Secret Milking Machine
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。