[bzoj]1930 pacman吃豆豆
生活随笔
收集整理的這篇文章主要介紹了
[bzoj]1930 pacman吃豆豆
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
Description
兩個(gè)PACMAN吃豆豆。一開始的時(shí)候，PACMAN都在坐標(biāo)原點(diǎn)的左下方，豆豆都在右上方。PACMAN走到豆豆處就會(huì)吃掉它。PACMAN行走的路線很奇怪，只能向右走或者向上走，他們行走的路線不可以相交。 請(qǐng)你幫這兩個(gè)PACMAN計(jì)算一下，他們倆加起來(lái)最多能吃掉多少豆豆。
Input
第一行為一個(gè)整數(shù)N，表示豆豆的數(shù)目。 接下來(lái) N 行，每行一對(duì)正整數(shù)，表示第i個(gè)豆豆的坐標(biāo)。任意兩個(gè)豆豆的坐標(biāo)都不會(huì)重合。
Output
僅有一行包含一個(gè)整數(shù)，即兩個(gè)PACMAN加起來(lái)最多能吃掉的豆豆數(shù)量
Sample Input
8
8 1
1 5
5 7
2 2
7 8
4 6
3 3
6 4
Sample Output
7
HINT
N < = 2000
Source
拼盡全力優(yōu)化，最后還是超時(shí)1個(gè)點(diǎn)。。。
裸的費(fèi)用流
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std; const int INF=0x7fffffff; struct Edge
{
int from,to,v,c,next;
}E[];
int node=;
int head[],from[],dis[],vis[]; int n,ans,S,T;
struct point
{
int x,y;
}P[]; int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-f;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} void ins(int from,int to,int v,int c)
{
node++;
E[node]=(Edge){from,to,v,c,head[from]};
head[from]=node;
} void insert(int from,int to,int v,int c)
{
ins(from,to,v,c);ins(to,from,,-c);
} bool spfa()
{
queue<int> Q;
for(int i=;i<=T;i++) dis[i]=-INF;
Q.push();dis[]=;vis[]=;
while(!Q.empty())
{
int q=Q.front();Q.pop();
for(int i=head[q];i;i=E[i].next)
if(E[i].v>&&dis[q]+E[i].c>dis[E[i].to])
{
dis[E[i].to]=dis[q]+E[i].c;
from[E[i].to]=i;
if(!vis[E[i].to])
{
Q.push(E[i].to);
vis[E[i].to]=;
}
}
vis[q]=;
}
return dis[T]!=-INF;
} void mcf()
{
int x=INF;
for(int i=from[T];i;i=from[E[i].from])
x=min(E[i].v,x);
for(int i=from[T];i;i=from[E[i].from])
{
ans+=x*E[i].c;
E[i].v-=x;E[i^].v+=x;
}
} bool cmp(point a,point b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
} int main()
{
n=read();T=*n+;S=T-;
for(int i=;i<=n;i++)
P[i].x=read(),P[i].y=read();
sort(P+,P+n+,cmp);
insert(,S,,);
for(int i=;i<=n;i++)
{
insert(S,i,,);
insert(i,i+n,,);
insert(i,i+n,,);
insert(i+n,T,,);
}
for(int i=;i<=n;i++)
{
int inf=INF;
for(int j=i+;j<=n;j++)
{
if(P[i].y<=P[j].y)
{
if(P[j].y<inf)
insert(i+n,j,,);
inf=min(inf,P[j].y);
}
}
}
while(spfa())
mcf();
printf("%d",ans);
return ;
}
總結(jié)
以上是生活随笔為你收集整理的[bzoj]1930 pacman吃豆豆的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 题解 CF1140D 【Minimum
- 下一篇： v-once