Bridges
Bridges
题目描述
YYD为了减肥,他来到了瘦海,这是一个巨大的海,海中有n个小岛,小岛之间有m座桥连接,两个小岛之间不会有两座桥,并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发,骑过每一座桥,到达每一个小岛,然后回到小岛1。霸中同学为了让YYD减肥成功,召唤了大风,由于是海上,风变得十分大,经过每一座桥都有不可避免的风阻碍YYD,YYD十分ddt,于是用泡芙贿赂了你,希望你能帮他找出一条承受的最大风力最小的路线。
输入
输入:第一行为两个用空格隔开的整数n(2<=n<=1000),m(1<=m<=2000),
接下来读入m行由空格隔开的4个整数a,b(1<=a,b<=n,a<>b),c,d(1<=c,d<=1000),
表示第i+1行第i座桥连接小岛a和b,从a到b承受的风力为c,从b到a承受的风力为d。
输出
输出:如果无法完成减肥计划,则输出NIE,否则第一行输出承受风力的最大值(要使它最小)
样例输入
4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
样例输出
4
提示
solution
题目不怎么严谨。。。
反正求一条欧拉回路,要求最大边权最小。
欧拉回路
无向图:所有点度数均为偶数且图联通。
有向图:所有点入度等于出度且图联通。
因为答案有单调性首先二分出mid,把大于mid的边拎出来。
这是一张混合图,我们给无向边先随便定一个向。
统计点的入度和出度,如果abs(in-out)&1 那么一定不合法。
因为翻转一条无向边会带来+-2的收益。
我们想怎么去维护欧拉回路。
若in[i]>out[i],则lj(S,i,(in[i]-out[i])/2)
否则lj(i,T,(out[i]-in[i])/2)。
判断最大流是否等于所有(in-out)/2(in>out)即可。
反向边流量我赋值成t3。。真是傻
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 1005
#define inf 1e9
using namespace std;
int n,m,l,r,Max,tot,S,T,head[maxn];
int in[maxn],out[maxn],d[maxn],flag[maxn],cur[maxn];
queue<int>q;
struct node{
int a,b,c,d;
}s[2002];
struct no{
int v,nex,cap;
}e[200005];
void lj(int t1,int t2,int t3){
e[++tot].v=t2,e[tot].cap=t3;e[tot].nex=head[t1];head[t1]=tot;
e[++tot].v=t1,e[tot].cap=0;e[tot].nex=head[t2];head[t2]=tot;
}
bool BFS(){
for(int i=1;i<=T;i++)d[i]=inf;
d[S]=0;q.push(S);
while(!q.empty()){
int x=q.front();q.pop();
cur[x]=head[x];
for(int i=head[x];i;i=e[i].nex){
if(d[e[i].v]>d[x]+1&&e[i].cap>0){
d[e[i].v]=d[x]+1;
if(!flag[e[i].v]){
flag[e[i].v]=1;q.push(e[i].v);
}
}
}
flag[x]=0;
}
return d[T]!=inf;
}
int lian(int k,int a){
if(k==T||!a)return a;
int f,flow=0;
for(int &i=cur[k];i;i=e[i].nex){
if(d[e[i].v]==d[k]+1&&(f=lian(e[i].v,min(e[i].cap,a)))>0){
e[i].cap-=f;e[i^1].cap+=f;
a-=f;flow+=f;
if(!a)break;
}
}
return flow;
}
bool pd(int mid)
{
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(head,0,sizeof(head));
tot=1;
for(int i=1;i<=m;++i)
{
if(s[i].c<=mid&&s[i].d<=mid){in[s[i].a]++,out[s[i].b]++,lj(s[i].a,s[i].b,1);continue;}
if(s[i].c<=mid)out[s[i].a]++,in[s[i].b]++;
else if(s[i].d<=mid)out[s[i].b]++,in[s[i].a]++;
else return false;
}
S=0;T=n+1;int sum=0,ans=0;
for(int i=1;i<=n;++i)
{
if((in[i]-out[i])%2)return false;
if(in[i]>out[i])lj(S,i,(in[i]-out[i])/2),sum+=(in[i]-out[i])/2;
else lj(i,T,(out[i]-in[i])/2);
}
while(BFS())ans+=lian(S,1e9);
return ans==sum;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&s[i].a,&s[i].b,&s[i].c,&s[i].d);
}
l=0,r=1005;
while(l<r){
int mid=(l+r)/2;
if(pd(mid))r=mid;
else l=mid+1;
}
if(r==1005)puts("NIE");
else cout<<r<<endl;
return 0;
}
假设定向(u,v)
那么就在网络流的图中连(v,u,1)
有流表示反向
最新文章
- Netty 系列之 Netty 高性能之道
- Spring-boot 开发Web应用
- MVC4项目中验证用户登录一个特性就搞定
- SQL Server2008ldf文件太大
- 用php实现遍历目录
- SQLyog 配置SQL Assitant
- 破解 crackme(完全拆解警告窗口)
- mysql SQL SERVER 的算法
- php中未定义变量的使用
- Java入门到精通——调错篇之解决MyEclipse 输入注册码后:Enter or update your subscription information.问题
- C++ Primer 学习笔记_67_面向对象编程 --转换与继承、复制控制与继承
- 使用XFire+Spring构建Web Service(一)——helloWorld篇
- CC++初学者编程教程(2) Microsoft Visual C++ 6.0开发环境搭建
- 搜狐畅游:每月给员工直系长辈2000元爱孝薪_企业新闻_265G产业频道
- CSS3的翻转效果
- 【CC2530入门教程-05】CC2530的串行接口原理与应用
- 浅谈快速开发框架的分层(WinForm)
- 最优Django环境配置
- 【SQL】SqlServer中Group By后,字符串合并
- cmd下可以启动java,输入javac提示 不“存在”
热门文章
- CUDA &;&; GPU中dim3介绍
- IDEA搭建Maven 的聚合项目
- 2013.10.26工作Fighting(1)
- Vue 父组件传值到子组件
- 爬虫学习(五)——使用handler管理器对象进行数据爬取的步骤
- python用requests请求,报SSL:CERTIFICATE_VERIFY_FAILED错误。
- SpringBoot显式事务
- Ansible学习 Inventory文件
- [BZOJ1208]宠物收养所(Splay)
- POJ 3370 Halloween treats(抽屉原理)