題意：
? ? ? n個區(qū)間，m種點，每種點有ci個，如果一個點的范圍在一個區(qū)間上，那么就可以消耗掉一個區(qū)間，問最多可以消耗多少個區(qū)間，就是這n個區(qū)間中，有多少個可能被抵消掉。


思路：
? ? ? 方法不唯一，首先可以用貪心來做，看到網(wǎng)上說的都是優(yōu)先隊列的解法，我說下我的想法，我是直接sort排序后暴力（其實根本達(dá)不到n*m*l的時間復(fù)雜度），我先把所有老牛也就是區(qū)間按照上端點（***不是他們說的下端點）從小打到排序，然后在把護(hù)膚品按照第一個值從小到大排序，然后就是給給每一個護(hù)膚品盡可能找到一個點，同時這個點的右端點盡可能的小，為了后面別的護(hù)膚品留下更大的機(jī)會，下面分析枚舉代碼
第i個護(hù)膚品的第j個和第k只奶牛


for(i = 1 ;i <= m ;i ++)
for(j = 1 ;j <= sp[i].c ;j ++)
{
? ? for(k = 1 ;k <= n ;k ++)
? ? if(!mark[k] && cow[k].l <= sp[i].p && cow[k].r >= sp[i].p)
? ? {
? ? ? ? ? ans ++;
? ? ? ? ? mark[k] = 1;
? ? ? ? ? break; ?
? ? }
? ? if(k == n + 1) 我個人覺得我加的這個地方可以很好的優(yōu)化掉很多數(shù)據(jù)，這么加的
? ? break; ? ? ? ? 依據(jù)是如果第i種護(hù)膚品的第j個不能給剩下的奶牛用了，那么第i種
} ? ? ? ? ? ? ? ? ?的其他的也沒用了，直接break

還有就是這個題目可以最大流來做，至于用那種算法，自己隨意吧，我用的是DINC,建圖比較簡單，我不想說了，如果你做過流的話一下就能想到建圖了，其實我感覺這個題目用最大流有點懸，但是AC了，因為邊的條數(shù)可能達(dá)到 （2500*2500+5000）* 2 = 12510000。

貪心 #include<stdio.h> #include<string.h> #include<algorithm>#define N 2500 + 10using namespace std;typedef struct {int l ,r; }COW;typedef struct {int p ,c; }SP;COW cow[N]; SP sp[N]; int mark[N];bool camp1(COW a ,COW b) {return a.r < b.r; }bool camp2(SP a ,SP b) {return a.p < b.p; }int main () {int n ,m, i ,j ,k;while(~scanf("%d %d" ,&n ,&m)){for(i = 1 ;i <= n ;i ++)scanf("%d %d" ,&cow[i].l ,&cow[i].r);for(i = 1 ;i <= m ;i ++)scanf("%d %d" ,&sp[i].p ,&sp[i].c);sort(cow + 1 ,cow + n + 1 ,camp1);sort(sp + 1 ,sp + m + 1 ,camp2);memset(mark ,0 ,sizeof(mark));int ans = 0;for(i = 1 ;i <= m ;i ++)for(j = 1 ;j <= sp[i].c ;j ++){for(k = 1 ;k <= n ;k ++)if(!mark[k] && cow[k].l <= sp[i].p && cow[k].r >= sp[i].p){ans ++;mark[k] = 1;break;}if(k == n + 1)break;}printf("%d\n" ,ans);}return 0; }DINIC#include<queue> #include<stdio.h> #include<string.h>#define N_node 2500 + 10 #define N_edge (2500 * 2500 + 5000) * 2 + 100 #define INF 1000000000using namespace std;typedef struct {int to ,cost ,next; }STAR;typedef struct {int x ,t; }DEP;typedef struct {int l ,r; }COW;typedef struct {int p ,c; }SP;COW cow[N_node]; SP sp[N_node]; STAR E[N_edge]; int list[N_node] ,list2[N_node] ,tot; int deep[N_node]; DEP xin ,tou;int minn(int x ,int y) {return x < y ? x : y; }void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot;E[++tot].to = a;E[tot].cost = 0;E[tot].next = list[b];list[b] = tot; }bool BFS_Deep(int s ,int t ,int n) {memset(deep ,255 ,sizeof(deep));xin.x = s ,xin.t = 0;deep[xin.x] = xin.t;queue<DEP>q;q.push(xin);while(!q.empty()){tou = q.front();q.pop();for(int k = list[tou.x] ;k ;k = E[k].next){int to = E[k].to;if(deep[to] != -1 || !E[k].cost)continue;xin.x = to ,xin.t = tou.t + 1;deep[xin.x] = xin.t;q.push(xin);}}for(int i = 0 ;i <= n ;i ++)list2[i] = list[i];return deep[t] != -1; }int DFS_Flow(int s ,int t ,int flow) {if(s == t) return flow;int nowflow = 0;for(int k = list2[s] ;k ;k = E[k].next){int to = E[k].to;int c = E[k].cost;list2[s] = k;if(deep[to] != deep[s] + 1 || !c)continue;int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));nowflow += tmp;E[k].cost -= tmp;E[k^1].cost += tmp;if(flow == nowflow) break;}if(!nowflow) deep[s] = 0;return nowflow; }int DINIC(int s ,int t ,int n) {int ans = 0;while(BFS_Deep(s ,t ,n)){ans += DFS_Flow(s ,t ,INF);}return ans; }int main () {int n ,m, i ,j;while(~scanf("%d %d" ,&n ,&m)){memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= n ;i ++){scanf("%d %d" ,&cow[i].l ,&cow[i].r);add(0 ,i ,1);}for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&sp[i].p ,&sp[i].c);add(i + n ,m + n + 1 ,sp[i].c);}for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++)if(cow[i].l <= sp[j].p && cow[i].r >= sp[j].p)add(i ,j + n ,1);printf("%d\n" ,DINIC(0 ,n + m + 1 ,n + m + 1));}return 0;}

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的POJ3614奶牛晒阳光DINIC或者贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。