题目大意:
有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具体怎么模拟呢。。。
我们把两种不同鼠标分别拍个序，首先取满所有的只能使用这个接口的电脑 然后对于两个接口都能使用的电脑，用一个类似于归并排序的过程即可。WoC,这么简单的题为什么当时我没想出来!!T的不要不要的费用流
#include#include #include 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 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 vchar 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#include #include using namespace std;typedef long long ll;template 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 <= 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;}