Codeforces 762B USB vs. PS/2 贪心

题目大意:

有a台只有USB接口的电脑,b台PS/2接口的电脑,c台两种接口都有的电脑。每台电脑只用装一个鼠标。给出n个鼠标及其费用，每个鼠标只能使用一遍。在最大化有鼠标的电脑数目的情况下最小化费用。

\((0 \le a,b,c \leq 10^5 , n \leq 3*10^5 )\)

题解:

这道题我们很容易抽象出来一个网络流模型

我们设超级源汇为S,T,每台电脑和鼠标都抽象成一个节点

我们可以这么建图

S -> 每台电脑 (flow = 1,cost = 0)

USB(PS/2)电脑 -> 所有USB(PS/2)鼠标(flow = 1,cost = 0)

双接口电脑 -> 所有鼠标(flow = 1,cost = 0)

所有鼠标 -> T (flow = 1,cost = \(cost_i\))

然后跑最小费用最大流即可

TLE

我们可以考虑简化构图，我们发现我们每台电脑只有三种连接可能，并且有一种链接方式是由其他的两种链接组成的，所以我们增设两个节点，分别连接所有的USB,PS/2鼠标，然后我们不用从电脑向每个鼠标都连边了，只用加在这两个点上就好了，边数大大减少

TLE

我们发现实际上同种鼠标之间并没有什么区别，所以我么把所有相同的鼠标也缩成一个点.这样把点数降低到了7个点，整张图上只有7个点。但边数还是有些大。。。

TLE

我CNMLGB !!!

我们发现把网络流化简到这个地步以后其实就是一个贪心。。

所以我们模拟这个贪心过程

具体怎么模拟呢。。。

我们把两种不同鼠标分别拍个序，首先取满所有的只能使用这个接口的电脑

然后对于两个接口都能使用的电脑，用一个类似于归并排序的过程即可。

WoC,这么简单的题为什么当时我没想出来!!

T的不要不要的费用流

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

inline int cat_max(const int &a,const int &b){return a>b ? a:b;}

inline int cat_min(const int &a,const int &b){return a<b ? a:b;}

const int maxn = 300010;

const int maxnode = 1024;

const int maxedge = maxn<<1;

const int inf = 0x3f3f3f3f;

struct Edge{

	int to,next,cap;

	ll cost;

}G[maxedge];

int head[maxnode],cnt=1;

inline void add(int u,int v,int c,ll d){

	G[++cnt].to = v;

	G[cnt].next = head[u];

	head[u] = cnt;

	G[cnt].cap = c;

	G[cnt].cost = d;

}

inline void insert(int u,int v,int c,ll d){

	add(u,v,c,d);add(v,u,0,-d);

}

#define v G[i].to

ll dis[maxnode],ans;int flow[maxnode];

const int lim = maxn<<1;

int q[lim + 10],p[maxnode];

int S,T,l,r,flo;bool inq[maxnode];

bool spfa(){

	memset(dis,0x3f,sizeof dis);

	dis[S] = 0;inq[S] = true;

	l = 0;r = -1;q[++r] = S;

	flow[S] = 0x3f3f3f3f;

	while(l <= r){

		int u = q[l % lim];++l;

		for(int i = head[u];i;i=G[i].next){

			if(dis[v] > dis[u] + G[i].cost && G[i].cap){

				dis[v] = dis[u] + G[i].cost;

				flow[v] = min(G[i].cap,flow[u]);

				p[v] = i;

				if(!inq[v]){

					inq[v] = true;

					q[++r % lim] = v;

				}

			}

		}inq[u] = false;

	}if(dis[T] == dis[0]) return false;

	ans += 1LL*flow[T]*dis[T];

	flo += flow[T];

	for(int u = T;u != S;u = G[p[u]^1].to)

		G[p[u]].cap -= flow[T],G[p[u]^1].cap += flow[T];

	return true;

}

#undef v

char s[10];

int main(){

	int a,b,c,n;read(a);read(b);read(c);

	read(n);

	int nodecnt = n;

	S = ++nodecnt;

	int node1 = ++nodecnt;insert(S,node1,a,0);

	int node2 = ++nodecnt;insert(S,node2,b,0);

	int node3 = ++nodecnt;insert(S,node3,c,0);

	int mob1 = ++nodecnt;

	int mob2 = ++nodecnt;

	int mob3 = ++nodecnt;

	int x;T = ++nodecnt;

	for(int i=1;i<=n;++i){

		read(x);scanf("%s",s);

		if(!strcmp(s,"USB")){

			insert(node1,mob1,inf,0);

			insert(node3,mob1,inf,0);

			insert(mob1,T,1,x);

		}else{

			insert(node2,mob2,inf,0);

			insert(node3,mob2,inf,0);

			insert(mob2,T,1,x);

		}

	}

	while(spfa());

	printf("%d %I64d\n",flo,ans);

	getchar();getchar();

	return 0;

}

正解的贪心

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

template<typename T>inline void read(T &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

inline int cat_max(const int &a,const int &b){return a>b ? a:b;}

inline int cat_min(const int &a,const int &b){return a<b ? a:b;}

const int maxn = 300010;

ll c1[maxn],cnt1;

ll c2[maxn],cnt2;

char s[10];

int main(){

	int a,b,c,n;read(a);read(b);read(c);

	read(n);ll x;

	for(int i=1;i<=n;++i){

		read(x);

		scanf("%s",s);

		if(!strcmp(s,"USB")){

			c1[++cnt1] = x;

		}else{

			c2[++cnt2] = x;

		}

	}

	sort(c1+1,c1+cnt1+1);

	sort(c2+1,c2+cnt2+1);

	int p1=0,p2=0;

	ll ans = 0;

	for(p1 = 1;p1 <= a && p1 <= cnt1; ++ p1) ans += c1[p1];

	for(p2 = 1;p2 <= b && p2 <= cnt2; ++ p2) ans += c2[p2];

	c1[cnt1+1] = c2[cnt2+1] = 1LL<<60;

	while(c){

		if(p1 > cnt1 && p2 > cnt2) break;

		if(c1[p1] < c2[p2]) ans += c1[p1++];

		else ans += c2[p2++];

		--c;

	}

	printf("%d %I64d\n",p1+p2-2,ans);

	getchar();getchar();

	return 0;

}

巴特西

Codeforces 762B USB vs. PS/2 贪心

题目大意:

题解:

最新文章

热门文章