HDU 1534 Schedule Problem(差分约束系统)
http://acm.hdu.edu.cn/showproblem.php?pid=1534
题意:有一个工程,它由N个部分构成,这N个部分都有一个连续的运行时间D[i]值,表示每一部分需要运行D[i]时间.现在的问题是,有M条约束条件需要满足,如FAS, FAF, SAF and SAS. FAS u v表示u部分的结束时间需要在v部分的开始时间之后.
问你该系统是否有解,如果有解的话,输出各个部分开始的时间.
分析:
我们令S[i]表示第i部分的开始时间,D[i]表示i部分运行的持续时间.
FAS u v 对应S[u]+D[u]>= S[v] 推出u到v的权值为D[u]的边
FAF u v 对应 S[u]+D[u]>=S[v]+D[v] 推出 u到v权值为D[u]-D[v]的边
SAF u v 对应 S[u]>=S[v]+D[v] 推出 u到v权值为-D[v]的边
SAS u v 对应 S[u]>=S[v] 推出u到v权值为0的边
构建有向图,由于该题可能无解,所以我们需要用超级源0号点去连接1到n号点.然后用BellmanFord算法判断是否有解.(用的是POJ1201提到的方案1)
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 1E9
using namespace std;
const int maxn=10000+10;
const int maxm=200000+10;
struct Edge
{
int from,to,dist;
Edge(){}
Edge(int f,int t,int d):from(f),to(t),dist(d){}
};
struct BellmanFord
{
int n,m;
int head[maxn],next[maxm];
Edge edges[maxm];
int d[maxn];
bool inq[maxn];
int cnt[maxn];
void init(int n)
{
this->n=n;
m=0;
memset(head,-1,sizeof(head));
}
void AddEdge(int from,int to,int dist)
{
edges[m]=Edge(from,to,dist);
next[m]=head[from];
head[from]=m++;
}
bool bellmanford()
{
memset(inq,0,sizeof(inq));
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++) d[i]= i==0?0:INF;
queue<int> Q;
Q.push(0);
while(!Q.empty())
{
int u=Q.front(); Q.pop();
inq[u]=false;
for(int i=head[u];i!=-1;i=next[i])
{
Edge &e=edges[i];
if(d[e.to] > d[u]+e.dist)
{
d[e.to] = d[u]+e.dist;
if(!inq[e.to])
{
inq[e.to]=true;
Q.push(e.to);
if(++cnt[e.to]>n) return true;
}
}
}
}
return false;
}
}BF;
int D[maxn];//任务持续时间
int main()
{
int n,kase=0;
while(scanf("%d",&n)==1&&n)
{
if(kase>0) printf("\n");
printf("Case %d:\n",++kase);
BF.init(n+1);
for(int i=1;i<=n;i++)
scanf("%d",&D[i]);
char s[100];
int u,v;
while(scanf("%s",s)==1&&s[0]!='#')
{
scanf("%d%d",&u,&v);
if(strcmp(s,"FAS")==0)
BF.AddEdge(u,v,D[u]);
else if(strcmp(s,"FAF")==0)
BF.AddEdge(u,v,D[u]-D[v]);
else if(strcmp(s,"SAF")==0)
BF.AddEdge(u,v,-D[v]);
else if(strcmp(s,"SAS")==0)
BF.AddEdge(u,v,0);
}
for(int i=1;i<=n;i++)
BF.AddEdge(0,i,0);
if(BF.bellmanford()) printf("impossible\n");
else
{
int min_v=0;
for(int i=1;i<=n;i++)
min_v=min(min_v,BF.d[i]);
for(int i=1;i<=n;i++)
printf("%d %d\n",i,BF.d[i]-min_v);//保证最小时间>=0
}
}
return 0;
}
分享到:
相关推荐
HDU 1022 Train Problem I 附详细思路
HDU图论题目分类
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu题目分类
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
1257 最低拦截系统 lis做的哦 详情可访问球球网 www.loveqiuqiu.com
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
其中有pku、hdu、zoj等各大oj的题目分类,pku的oj比较详细一点,按不同算法进行分类,均系从网上自行搜集的。
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
杭电操作系统实验 HDU操作系统实验.zip
搜索 dfs 解题代码 hdu1241
hdu ACM代码 每种算法都有分类 大三了,没有时间弄ACM,这些要删了
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。