C语言的数据类型
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C语言的数据类型,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4593字,纯文字阅读大概需要7分钟。
内容图文
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8660 | Accepted: 2599 |
Description
The farm comprises N (2 <= N <= 200) landmarks (numbered 1..N) connected by P (1 <= P <= 40,000) bidirectional trails (numbered 1..P) and with a positive length that does not exceed 1,000,000. Multiple trails might join a pair of landmarks.
To minimize his chances of detection, FJ knows he cannot use any trail on the farm more than once and that he should try to use the shortest trails.
Help FJ get from the barn (landmark 1) to the secret milking machine (landmark N) a total of T times. Find the minimum possible length of the longest single trail that he will have to use, subject to the constraint that he use no trail more than once. (Note well: The goal is to minimize the length of the longest trail, not the sum of the trail lengths.)
It is guaranteed that FJ can make all T trips without reusing a trail.
Input
* Lines 2..P+1: Line i+1 contains three space-separated integers, A_i, B_i, and L_i, indicating that a trail connects landmark A_i to landmark B_i with length L_i.
Output
Sample Input
7 9 2 1 2 2 2 3 5 3 7 5 1 4 1 4 3 1 4 5 7 5 7 1 1 6 3 6 7 3
Sample Output
5
Hint
Huge input data,scanf is recommended.
Source
题意: 找k条不相交的路径,使得最大边的权值最小,
解题思路:二分权值,然后建图,跑最大流,记着是双向边,单向边wa了好多次。
代码:
/* *********************************************** Author :xianxingwuguan Created Time :2014-1-25 14:49:49 File Name :3.cpp ************************************************ */ #pragma comment(linker, "/STACK:102400000,102400000") #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; typedef int ll; const ll inf=10000000; const ll maxn=2000; ll head[maxn],tol,dep[maxn]; struct node { ll from,to,next,cap; node(){}; node(ll from,ll to, ll next,ll cap):from(from),to(to),next(next),cap(cap){} }edge[1000000],ss[1000000]; void add(ll u,ll v,ll cap) { edge[tol]=node(u,v,head[u],cap); head[u]=tol++; edge[tol]=node(v,u,head[v],0); head[v]=tol++; } bool bfs(ll s,ll t) { ll que[maxn],front=0,rear=0; memset(dep,-1,sizeof(dep)); dep[s]=0;que[rear++]=s; while(front!=rear) { ll u=que[front++];front%=maxn; for(ll i=head[u];i!=-1;i=edge[i].next) { ll v=edge[i].to; if(edge[i].cap>0&&dep[v]==-1) { dep[v]=dep[u]+1; que[rear++]=v; rear%=maxn; if(v==t)return 1; } } } return 0; } ll dinic(ll s,ll t) { ll res=0; while(bfs(s,t)) { ll Stack[maxn],top,cur[maxn]; memcpy(cur,head,sizeof(head)); top=0; ll u=s; while(1) { if(t==u) { ll min=inf; ll loc; for(ll i=0;i<top;i++) if(min>edge[Stack[i]].cap) { min=edge[Stack[i]].cap; loc=i; } for(ll i=0;i<top;i++) { edge[Stack[i]].cap-=min; edge[Stack[i]^1].cap+=min; } res+=min; top=loc; u=edge[Stack[top]].from; } for(ll i=cur[u];i!=-1;cur[u]=i=edge[i].next) if(dep[edge[i].to]==dep[u]+1&&edge[i].cap>0)break; if(cur[u]!=-1) { Stack[top++]=cur[u]; u=edge[cur[u]].to; } else { if(top==0)break; dep[u]=-1; u=edge[Stack[--top]].from; } } } return res; } int main() { int n,m,t,i,j,k; while(cin>>n>>m>>t) { int left=inf,right=-inf; for(i=1;i<=m;i++) { scanf("%d%d%d",&ss[i].from,&ss[i].to,&ss[i].cap); if(left>ss[i].cap)left=ss[i].cap; if(right<ss[i].cap)right=ss[i].cap; } right=1000000; int ans; while(left<=right) { memset(head,-1,sizeof(head));tol=0; int mid=(left+right)>>1; for(i=1;i<=m;i++) if(ss[i].cap<=mid) add(ss[i].from,ss[i].to,1),add(ss[i].to,ss[i].from,1); if(dinic(1,n)>=t)right=mid-1,ans=mid; else left=mid+1; } cout<<ans<<endl; } return 0; }
原文:http://blog.csdn.net/abc5382334/article/details/18777957
内容总结
以上是互联网集市为您收集整理的C语言的数据类型全部内容,希望文章能够帮你解决C语言的数据类型所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。