hdu3572

hdu3572
题意
有n 个任务 m个 机器 每个任务有一个约束 就是在si 开始 ti结束可以取到边界 要做pi天

每一个机器一天只能去做一个任务，问能不能完成所有任务

有几个约束
1 每个任务从si 到ti 里任意选 pi 天
2 每天只能最多m个机器工作 也就是去完成m个不同的任务

要用到的类
任务 天
分析
每一个任务 匹配 si 到ti 的天数 让其匹配的关系 流为1
那么每一个任务流入的流为pi
每一个天流出的流也就为m

dinic

//#include 
#include
#includeusing namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=1010;
const int maxm=maxn*maxn;
ll N,M;
struct point
{int s,e;ll p;
};
point pp[maxn];
struct edge
{int v,next;ll w;
};
edge no[maxm];
int head[maxn];
int level[maxn];
int cnt;
queue <int> q;
int __=0;
bool bfs(int s,int t,int n)
{for(int i=0;i<=n;i++)level[i]=-1;while(!q.empty()){q.pop();}q.push(s);level[s]=0;while(!q.empty()){int u=q.front();if(u==t)return true;q.pop();for(int i=head[u];i;i=no[i].next){int v=no[i].v;ll w=no[i].w;if(w>0&&level[v]==-1){level[v]=level[u]+1;q.push(v);}}}return false;
}
ll dfs(int u,int t,ll max_)
{if(u==t)return max_;ll sum=0;for(int i=head[u];i;i=no[i].next){edge & e=no[i];if(e.w>0&&level[e.v]==level[u]+1){ll f=dfs(e.v,t,min(max_-sum,e.w));sum+=f;no[i].w-=f;no[1+((i-1)^1)].w+=f;if(sum==max_)break;}}if(!sum)level[u]=-1;return sum;
}
ll dinic(int s,int t,int n)
{ll ans=0;while(bfs(s,t,n)){ll f;while((f=dfs(s,t,INF))>0)ans+=f;}return ans;
}
void init()
{cnt=1;for(int i=0;i<maxn;i++){head[i]=0;}
}
void add(int x,int y,ll w)
{no[cnt].v=y;no[cnt].w=w;no[cnt].next=head[x];head[x]=cnt;cnt++;
}
void solve()
{///M个机器int s=0;///源点ll ans=0;int t=1005;///汇点for(int i=1;i<=N;i++)///N个任务{///p天完成  s天开始  e结束可以取到边缘cin>>pp[i].p>>pp[i].s>>pp[i].e;ans+=pp[i].p;}for(int i=1;i<=N;i++){add(s,i,pp[i].p);add(i,s,0);}for(int i=1;i<=N;i++){for(int j=pp[i].s;j<=pp[i].e;j++){add(i,j+N,1);add(j+N,i,0);}}for(int i=1;i<=500;i++){add(i+N,t,M);add(t,i+N,0);}cout<<"Case "<<__<<": ";if(dinic(s,t,1005)==ans)cout<<"Yes"<<"\n\n";elsecout<<"No"<<"\n\n";}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int T=1;cin>>T;while(T--){__++;cin>>N>>M;init();solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！