題目鏈接：點擊查看

題目大意：給出n頭奶牛，奶牛們現在要曬太陽，每頭奶牛需要[l,r]區間內的光照強度，現在有m種防曬霜，每種防曬霜可以讓奶牛接受到val數值的光照強度，然后每種防曬霜只有num個，現在問在合理分配防曬霜后，最多能有多少頭奶牛可以曬太陽

題目分析：一開始是想貪心做的，但是無奈不會，想了一會知道是排序但不知道怎么排，又觀察了一下這個題目，發現就是個二分圖多重匹配問題啊，讓奶牛去匹配防曬霜就行了，而且數據范圍也正好是匈牙利算法可以接受的范圍，這樣一來就好辦了，直接建圖，對匈牙利的內部實現稍作修改就可以了

A了這個題目后還是不甘心，去看了看貪心的題解，發現是對防曬霜的val升序排序，然后對每頭奶牛的區間按照右端點r升序排序即可，因為對于一個防曬霜，我們會盡可能的找右端點最小的奶牛與其匹配，因為右端點更大的奶牛可以有更多的選擇，所以這樣就形成了一個貪心的策略，按照這個策略貪心即可

代碼：

二分圖多重匹配：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<deque> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=3e3+100;int n,m;struct Node {int l,r; }a[N];struct NODE {int val,num; }b[N];bool vis[N];vector<int>match[N];vector<int>node[N];//記得用鄰接表，鄰接矩陣會超時bool dfs(int x) {for(int i=0;i<node[x].size();i++){int to=node[x][i];if(!vis[to]){vis[to]=true;if(match[to].size()<b[to].num){match[to].push_back(x);return true;}for(int j=0;j<match[to].size();j++){if(dfs(match[to][j])){match[to][j]=x;return true;}}}}return false; }void init() {for(int i=1;i<N;i++){match[i].clear();node[i].clear();} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);for(int i=1;i<=m;i++)scanf("%d%d",&b[i].val,&b[i].num);for(int i=1;i<=n;i++)//建邊for(int j=1;j<=m;j++)if(a[i].l<=b[j].val&&b[j].val<=a[i].r)node[i].push_back(j);int ans=0;for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}printf("%d\n",ans);}return 0; }

貪心：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<deque> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=3e3+100;struct Cow {int l,r;bool operator<(const Cow& a)const{if(r!=a.r)return r<a.r;return l<a.l;} }a[N];struct Node {int val,num;bool operator<(const Node& a)const{return val<a.val;} }b[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);for(int i=1;i<=m;i++)scanf("%d%d",&b[i].val,&b[i].num);sort(a+1,a+1+n);sort(b+1,b+1+m);int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!b[j].num)continue;if(a[i].l<=b[j].val&&b[j].val<=a[i].r){b[j].num--;ans++;break;}}}printf("%d\n",ans);}return 0; }

網絡流-最大流：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<deque> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e3+100;struct Node {int a,b; }a[N/2],b[N/2];struct Edge {int to,w,next; }edge[N*N];int head[N],cnt;void addedge(int u,int v,int w) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].to=u;edge[cnt].w=0;edge[cnt].next=head[v];head[v]=cnt++; }int d[N],now[N*N];bool bfs(int s,int t) {memset(d,0,sizeof(d));queue<int>q;q.push(s);now[s]=head[s];d[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;int w=edge[i].w;if(!w||d[v])continue;now[v]=head[v];d[v]=d[u]+1;q.push(v);if(v==t)return true;}}return false; }int dinic(int x,int t,int flow) {if(x==t)return flow;int rest=flow,i;for(i=now[x];i!=-1&&rest;i=edge[i].next){int v=edge[i].to;int w=edge[i].w;if(w&&d[v]==d[x]+1){int k=dinic(v,t,min(flow,w));if(!k)d[v]=0;edge[i].w-=k;edge[i^1].w+=k;rest-=k;}}now[x]=i;return flow-rest; }void init() {memset(head,-1,sizeof(head));cnt=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF){init(); int s=n+m+1,t=n+m+2;for(int i=1;i<=n;i++)scanf("%d%d",&a[i].a,&a[i].b);for(int i=1;i<=m;i++)scanf("%d%d",&b[i].a,&b[i].b);for(int i=1;i<=n;i++)addedge(s,i,1);for(int i=1;i<=m;i++)addedge(i+n,t,b[i].b);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i].a<=b[j].a&&b[j].a<=a[i].b)addedge(i,j+n,1);int flow,ans=0;while(bfs(s,t))while(flow=dinic(s,t,inf))ans+=flow;printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 3614 Sunscreen(贪心/二分图最大匹配-多重匹配/网络流-最大流)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。