首页 > 代码库 > hdoj 2883 kebab 【经典最大流】
hdoj 2883 kebab 【经典最大流】
题目:hdoj 2883 kebab
题意:现在有n个人要烤肉,有m个烤肉架,然后给出每个人的烤肉开始时间si,结束时间ei,以及要烤肉的串数num,还有拷一串的时间ti,然后问你能不能满足所有人的要求。
分析:这是一个比较经典的最大流,经典在于建图方法,这个题目难点在于时间跨度在0---100 0000,如果时间短的话就可以用题目3572的做法了。点击打开链接
后面看了别人的建图方法,确实比较经典,经典在于把区间缩点了,这个题目的难点在于时间跨度大,那么我们可以把所有的时间点记录下来,然后排序,然后以这些时间点建图。
建图方案:
首先超级源点s到每个人 i 建容量为 num * ti 边,
然后对于每个人的烤肉时间区间,枚举排序之后的所有的相邻时间点,相邻两点也组成一个区间,那么假如枚举的区间包含在这个人的时间区间内,从人 i 建边 区间 j,容量inf
然后每个区间开始点 j 建边到超级汇点建边容量为(time【j+1】-time【j】)*m。
这样,如果最大流为所有的count(num * ti),则满足要求。
样例1建图之后得到这样的图:
这个题目也是用c++提交的,G++编译错误,不解。
AC代码:
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> using namespace std; #define Del(a,b) memset(a,b,sizeof(a)) const int N = 1020; const int inf = 0x3f3f3f3f; int n,m; int Min(int a,int b) { return a>b?b:a; } struct Node { int from,to,cap,flow; }; vector<int> v[N]; vector<Node> e; int vis[N]; //构建层次图 int cur[N]; void add_Node(int from,int to,int cap) { Node tmp1,tmp2; tmp1.cap=from=from,tmp1.to=to,tmp1.cap=cap,tmp1.flow=0; e.push_back(tmp1); tmp2.from=to,tmp2.to=from,tmp2.cap=0,tmp2.flow=0; e.push_back(tmp2); int tmp=e.size(); v[from].push_back(tmp-2); v[to].push_back(tmp-1); } bool bfs(int s,int t) { Del(vis,-1); queue<int> q; q.push(s); vis[s] = 0; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i<v[x].size();i++) { Node tmp = e[v[x][i]]; if(vis[tmp.to]<0 && tmp.cap>tmp.flow) //第二个条件保证 { vis[tmp.to]=vis[x]+1; q.push(tmp.to); } } } if(vis[t]>0) return true; return false; } int dfs(int o,int f,int t) { if(o==t || f==0) //优化 return f; int a = 0,ans=0; for(int &i=cur[o];i<v[o].size();i++) //注意前面 ’&‘,很重要的优化 { Node &tmp = e[v[o][i]]; if(vis[tmp.to]==(vis[o]+1) && (a = dfs(tmp.to,Min(f,tmp.cap-tmp.flow),t))>0) { tmp.flow+=a; e[v[o][i]^1].flow-=a; //存图方式 ans+=a; f-=a; if(f==0) //注意优化 break; } } return ans; //优化 } int dinci(int s,int t) { int ans=0; while(bfs(s,t)) { Del(cur,0); int tm=dfs(s,inf,t); ans+=tm; } return ans; } struct Node1 { int si,num,ei,ti; }; Node1 a[250]; vector<int> time; int main() { //freopen("Input.txt","r",stdin); int n,m; while(~scanf("%d%d",&n,&m)) { int s=0,t=3*n+2,count=0,i,j; for(i=1;i<=n;i++) { scanf("%d%d%d%d",&a[i].si,&a[i].num,&a[i].ei,&a[i].ti); time.push_back(a[i].si); time.push_back(a[i].ei); int tmp = a[i].num*a[i].ti; count+=tmp; add_Node(s,i,tmp); } sort(time.begin(),time.end()); for(i=1;i<=n;i++) { for(j=0;j<(time.size()-1);j++) { if(a[i].si<=time[j] && a[i].ei>=time[j+1]){ add_Node(i,n+j+1,inf); //printf("-%d ",time[j]); } } } for(i=0;i<(time.size()-1);i++) add_Node(n+i+1,t,(time[i+1]-time[i])*m); int ans=dinci(s,t); //printf("%d\n",ans); if(ans==count) printf("Yes\n"); else printf("No\n"); for(i=0;i<=t;i++) v[i].clear(); e.clear();time.clear(); } return 0; }
hdoj 2883 kebab 【经典最大流】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。