题意
有n个项目, m台机器,一台机器同一时间只能完成一个项目, 一个项目可以在多个机器上完成, 给出这n个项目可以开始建设的时间和截止时间及需要多少天完成, 问是否可以在规定时间内完成所有项目
分析
1 建立模型, 用什么方法解决这种问题, 我们看到一天之内最多可以完成m个工作量, 完成一个项目需要的工作量, 这些都可以用流来表示, 于是选择最大流算法
2 建图, 首先确定什么是结点, 什么是边,
(1) 每一天都可以是一个结点, 经过这个节点的最大流量是m,
(2)其次每个任务都可以是一个结点, 这些结点的流量应该等于该任务的完成时间,
(3) 再次, 确定一个源点和汇点
(4) 可以在源点与任务点之间建立边, 边的容量正是完成该任务的时间
(5)在一个任务的开始和截止时间这些天里, 把每一天都与该任务相连,边的容量为1, 表示一天之内一个任务的总时间只能减少1, 不存在同时做一件任务的情况
(6)在每一天与汇点之间建立边, 边的容量是m
3 建图之后套用dinic算法模版(如要详细了解, 刘汝佳算法竞赛训练指南p358)即
参考代码
const int LEN = 1100;
const int maxn = 1e8;
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int w,int f): from(u),to(v),cap(w),flow(f){}
};
struct Dinic{
int n,m,s,t;
vector<Edge> edges;//存边
vector<int> G[LEN];//结点
int vis[LEN];//bfs需要标记是否访问过该点
int d[LEN];//表示源点到该点的层次
int cur[LEN];//代表dfs已经搜到了那个点
void init(int n)//初始化
{
this->n = n;
for(int i = 0;i < n; ++i)
G[i].clear();
edges.clear();
}
void Add(int u,int v,int w)//添加边
{
edges.push_back(Edge(u,v,w,0));
edges.push_back(Edge(v,u,0,0));
m = edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool Bfs(void)//分层
{
me(d);
me(vis);
d[s] = 0;
vis[s] = 1;
queue<int> Q;//队列进行广搜
Q.push(s);
while(!Q.empty())
{
int q = Q.front();Q.pop();
for(size_t i = 0;i < G[q].size();++i)
{
Edge &tmp = edges[G[q][i]];
if(!vis[tmp.to]&&tmp.cap>tmp.flow)
{
vis[tmp.to] = 1;
d[tmp.to] = d[q] + 1;//结点层次是上一次的加一
Q.push(tmp.to);
}
}
}
return vis[t];
}
int Dfs(int node,int a)
{
if(node == t||a == 0)//如果搜到了汇点或者分配到当前节点的流量为零, 返回
return a;
int flow = 0,f;
for(int &i = cur[node];i < G[node].size();++i)//注意用的是引用
{
Edge &tmp = edges[G[node][i]];//同样也是引用
if(d[tmp.to]==d[node]+1&&(f = Dfs(tmp.to,min(a,tmp.cap-tmp.flow)))>0)
{
flow += f;
tmp.flow += f;
edges[G[node][i]^1].flow -= f;//修改路径
a -= f;
if(a==0)
break;
}
}
return flow;
}
int MaxFlow(int s,int t)
{
this->s = s;
this->t = t;
int flow = 0;
while(Bfs())
{
me(cur);
flow += Dfs(s,maxn);
}
return flow;
}
};
Dinic dinic;
int p[LEN];
int e[LEN];
int s[LEN];
int main()
{
int N,M,S,T;
int t,kase = 0;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&N,&M);
S = 0, T = 1000;//源点设为零, 汇点设为一千
dinic.init(1000+10);
// int u,v,w;
int sum = 0;
for(int i = 0;i < N;++i)
{
scanf("%d %d %d",&p[i],&s[i],&e[i]);
sum += p[i];
}
for(int i = 1;i <= 500; ++i)
{
dinic.Add(i,T,M);//在每一天到汇点之间建立边
}
for(int i = 0;i < N; ++i)
{
dinic.Add(S,501+i,p[i]);//在源点到各个人物之间建立边
for(int j = s[i];j <= e[i];++j)
{
dinic.Add(501+i,j,1);//在各任务时间内每一天与与该任务建立边
}
}
int ans = 0;
ans = dinic.MaxFlow(S,T);
if(ans == sum)
printf("Case %d: Yes\n",++kase);
else
printf("Case %d: No\n",++kase);
// if(t)
printf("\n");
}
return 0;
}
京公网安备 11010502036488号