吃豆豆
题目描述
两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。 请你帮这两个PACMAN计算一下，他们俩加起来最多能吃掉多少豆豆。
输入格式
第一行为一个整数N，表示豆豆的数目。 接下来 N 行，每行一对正整数，表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。
输出格式
仅有一行包含一个整数，即两个PACMAN加起来最多能吃掉的豆豆数量
输入输出样例
输入 #1 复制
8
8 1
1 5
5 7
2 2
7 8
4 6
3 3
6 4
输出 #1 复制
7
说明/提示
N < = 2000
纪念自己洛谷第一道黑题。。。。。
看到这道题，我们会想到跑费用流，但是由于点数太多，我们不能一一去连边，这样肯定会TLE，那我们就需要做一些剪枝了，对于每个点先按照x坐标排序，然后对于每个点我们肯定只能连到它右上的点。然后假设我们现在已经连了右上的第一个点，那我们怎么做呢？对于连了这个点的后面的比我们连的这个点y坐标大的话，那么这个点肯定会被我们第一个连的点所相连，这样这个点就是不需要相连的，然后跑一次费用流即可。
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10,M=1e6+10;
int n,S,T,v[N],e[N],d[N];
int head[N],nex[M],w[M],to[M],flow[M],tot=1;
struct node{
int x,y;
}t[N];
int cmp(const node a,const node b){
if(a.x!=b.x) return a.x<b.x; return a.y<b.y;
}
inline void ade(int a,int b,int c,int d){
to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
ade(a,b,c,d); ade(b,a,0,-d);
}
int spfa(){
memset(d,0xcf,sizeof d); queue<int> q; q.push(S);
d[S]=0; int vis[N]={0}; vis[S]=1;
while(q.size()){
int u=q.front(); q.pop(); vis[u]=0;
for(int i=head[u];i;i=nex[i]){
if(flow[i]>0&&d[to[i]]<d[u]+w[i]){
d[to[i]]=d[u]+w[i];
v[to[i]]=u; e[to[i]]=i;
if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
}
}
}
return d[T]!=0xcfcfcfcf;
}
int EK(){
int res=0;
while(spfa()){
int mi=0x3f3f3f3f;
for(int i=T;i!=S;i=v[i]) mi=min(mi,flow[e[i]]);
for(int i=T;i!=S;i=v[i]) flow[e[i]]-=mi,flow[e[i]^1]+=mi;
res+=mi*d[T];
}
return res;
}
signed main(){
cin>>n; S=4*n+1; T=S+1; int m=n+1;
for(int i=1;i<=n;i++) cin>>t[i].x>>t[i].y;
t[0].x=t[0].y=0;
sort(t+1,t+1+n,cmp); add(S,0,2,0);
for(int i=0;i<=n;i++){
int mi=0;
for(int j=i+1;j<=n;j++){
if(t[i].y>t[j].y) continue;
if((!mi)||t[j].y<mi){
add(i+m,j,2,0); mi=t[j].y;
}
}
}
add(0,m,2,0);
for(int i=1;i<=n;i++) add(i,i+m,1,1),add(i,i+m,1,0),add(i+m,T,2,0);
cout<<EK()<<endl;
return 0;
}
文章创建于: 2019-08-22 08:26:44
相关阅读
我是偷偷完了一个月游戏，必须交点作业，所以写了这篇文章。增长黑客（Growth hacking）是一套来自美国硅谷的创业法则，核心是数据驱动的实
凡是入驻淘宝汇吃的商家，都必须遵守淘宝汇吃都规则，其中最严格的就是标签，所有商品必须有淘宝汇吃标签，而且还得符合一定的要求，今天我
目录 1.实现效果： 2.游戏玩法 3.需求分析 4.代码实现 1.实现效果： 2.游戏玩法 该游戏用上下左右控制蛇的方向，寻找吃的东西，每
近期，IG夺冠的信息火遍了大江南北，但比之更加火热的，却是老板王思聪吃热狗的照片。演员明星们费尽心思都难上的热搜，却被王思聪频频登
A5创业网(公众号:iadmin5)10月3日讯，近日又一名网红诞生，华农兄弟因拍养殖和吃竹鼠视频而爆红网络!一名叫华农兄弟的网友因为他养殖