POJ 2391 floyd二分+拆点+最大流
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 20904 | Accepted: 4494 |
Description
The farm has F (1 <= F <= 200) fields on which the cows graze. A set of P (1 <= P <= 1500) paths connects them. The paths are wide, so that any number of cows can traverse a path in either direction.
Some of the farm's fields have rain shelters under which the cows can shield themselves. These shelters are of limited size, so a single shelter might not be able to hold all the cows. Fields are small compared to the paths and require no time for cows to traverse.
Compute the minimum amount of time before rain starts that the siren must be sounded so that every cow can get to some shelter.
Input
* Lines 2..F+1: Two space-separated integers that describe a field. The first integer (range: 0..1000) is the number of cows in that field. The second integer (range: 0..1000) is the number of cows the shelter in that field can hold. Line i+1 describes field i.
* Lines F+2..F+P+1: Three space-separated integers that describe a path. The first and second integers (both range 1..F) tell the fields connected by the path. The third integer (range: 1..1,000,000,000) is how long any cow takes to traverse it.
Output
Sample Input
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
Sample Output
110
解析 先求一遍两点之间的最短距离 然后二分答案mid,每次二分的时候构建一个网络 两点之间的距离<=mid 连一条有向边 不过要拆点 保证使它是单向的,避免不可达的可达,
跑一边最大流 如果等于牛的总数 说明mid时间内可以的到达 继续二分 出最优答案。
我为什么感觉可以费用流解决。。。有时间试一试
#include<iostream>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=1e3+,mod=1e9+;
const ll inf=1e16;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n");
#define debug(a,b) cout<<a<<" "<<b<<" ";
ll min(ll a,ll b){return a>b?b:a;}
struct edge
{
int from,to,c,f;
edge(int u,int v,int c,int f):from(u),to(v),c(c),f(f) {}
};
int n,m,N;
vector<edge> edges;
vector<int> g[maxn];
int d[maxn];//从起点到i的距离
int cur[maxn];//当前弧下标
ll dp[maxn][maxn];
ll a[maxn],b[maxn],sum;
void init(int n)
{
for(int i=; i<=N; i++) g[i].clear();
edges.clear();
}
void addedge(int from,int to,int c) //加边 支持重边
{
edges.push_back(edge(from,to,c,));
edges.push_back(edge(to,from,,));
int siz=edges.size();
g[from].push_back(siz-);
g[to].push_back(siz-);
}
int bfs(int s,int t) //构造一次层次图
{
memset(d,-,sizeof(d));
queue<int> q;
q.push(s);
d[s]=;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=;i<g[x].size();i++)
{
edge &e=edges[g[x][i]];
if(d[e.to]<&&e.f<e.c) //d[e.to]=-1表示没访问过
{
d[e.to]=d[x]+;
q.push(e.to);
}
}
}
return d[t];
}
int dfs(int x,int a,int t) // a表示x点能接收的量
{
if(x==t||a==)return a;
int flow=,f;//flow总的增量 f一条增广路的增量
for(int &i=cur[x];i<g[x].size();i++)//cur[i] &引用修改其值 从上次考虑的弧
{
edge &e=edges[g[x][i]];
if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.c-e.f),t))>) //按照层次图增广 满足容量限制
{
e.f+=f;
edges[g[x][i]^].f-=f; //修改流量
flow+=f;
a-=f;
if(a==) break;
}
}
return flow;
}
int maxflow(int s,int t)
{
int flow=;
while(bfs(s,t)!=-)
{
memset(cur,,sizeof(cur));
flow+=dfs(s,0x3f3f3f3f,t);
}
return flow;
}
void build(ll x)
{
init(N);
for(int i=;i<=n;i++)
{
addedge(,i,a[i]);
addedge(i+n,N,b[i]);
addedge(i,i+n,0x3f3f3f3f);
}
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
{
if(dp[i][j]<=x)
{
addedge(i,j+n,0x3f3f3f3f);
addedge(j,i+n,0x3f3f3f3f);
}
}
}
}
ll solve()
{
ll ans=-;
ll l=,r=inf-;
while(l<=r)
{
ll mid=(l+r)/;
build(mid);
int temp=maxflow(,N);
//cout<<mid<<" "<<temp<<endl;
if(temp>=sum)
{
ans=mid;
r=mid-;
}
else l=mid+;
}
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
N=n*+;sum=;
for(int i=;i<=n;i++)
{
scanf("%ld%ld",&a[i],&b[i]);
sum+=a[i];
}
//====================floyd==========================//
for(int i=; i<=n; i++)
for(int j=; j<=n; j++) //初始化长度
{
if(i==j)
dp[i][j]=;
else
dp[i][j]=inf;
}
ll x,y,d;
for(int i=;i<m;i++)
{
scanf("%lld%lld%lld",&x,&y,&d);
if(dp[x][y]>d)
dp[x][y]=dp[y][x]=d;
}
for(int k=; k<=n; k++)
for(int i=; i<=n; i++)
if(dp[i][k]!=inf)
for(int j=; j<=n; j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
//=========================================================//
//init(n);
cout<<solve()<<endl;
}
}
最新文章
- Material Design 概念,环境和基本属性
- iOS 10 :用 UIViewPropertyAnimator 编写动画
- Tutorial - Deferred Rendering Shadow Mapping 转
- python的metaclass
- jmeter 构建一个FTP测试计划
- 【quartz】 理论知识
- C# 在vs2010中打开vs2012的项目(转)
- bzoj 1200: [HNOI2005]木梳 DP
- SpringMVC源码解析 - HandlerMethod
- mysql存储过程详解[转]
- 看Lucene源码必须知道的基本概念
- C#中 计时器用法
- 如何在ASP.NET Core中使用JSON Patch
- Windows 10 远程连接出现函数错误 【这可能由于CredSSP加密Oracle修正】
- 给大家一些改善 Python 程序的 91 个建议
- mipi LCD 的CLK时钟频率与显示分辨率及帧率的关系【转】
- Dubbo 在maven项目中的应用
- Java虚拟机(一)结构原理与运行时数据区域
- oracle 列相减——(Oracle分析函数Lead(),Lag())
- Java 下一代: 函数式编码风格&mdash;&mdash;Groovy、Scala 和 Clojure 共享的函数结构及其优势