poj 1698

57 阅读 0 评论 38 点赞

我是靠谱客的博主专注航空，最近开发中收集的这篇文章主要介绍poj 1698，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意:爱丽丝喜欢拍电影,现在正好有N个公司找她拍电影,每部电影都指定在每周的星期几拍,要用D天拍完电影,最迟M个星期要拍完.问爱丽丝能不能拍完所有电影.

分析:350天各为一个顶点,每个顶点都有且只有一条边指向汇点t,容量为1,源点为爱丽丝,指向每部电影,权值为该部电影拍完的天数D,每部电影都向能拍这部电影的那一天的顶点建一条权值为1的边.如果计算出来的最大流为所有电影要拍的天数的总和则能够拍完所有电影,否则不能.


1 #include <cstdio>

2 #include <cstring>

3 const int MAXN=375;//点数的最大值

4 const int MAXM=14740;//边数的最大值

5 const int INF=0x3fffffff;

6

7 struct Node

8 {

9
int from,to,next;
 10
int cap;
 11 }edge[MAXM];
 12
 13 int tol;
 14 int head[MAXN];
 15 int dep[MAXN];
 16 int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y
 17
 18 int n;//n是总的点的个数，包括源点和汇点
 19
 20 void init()
 21 {
 22
tol=0;
 23
memset(head,-1,sizeof(head));
 24 }
 25
 26 void addedge(int u,int v,int w)
 27 {
 28
edge[tol].from=u;
 29
edge[tol].to=v;
 30
edge[tol].cap=w;
 31
edge[tol].next=head[u];
 32
head[u]=tol++;
 33
edge[tol].from=v;
 34
edge[tol].to=u;
 35
edge[tol].cap=0;
 36
edge[tol].next=head[v];
 37
head[v]=tol++;
 38 }
 39 void BFS(int start,int end)
 40 {
 41
memset(dep,-1,sizeof(dep));
 42
memset(gap,0,sizeof(gap));
 43
gap[0]=1;
 44
int que[MAXN];
 45
int front,rear;
 46
front=rear=0;
 47
dep[end]=0;
 48
que[rear++]=end;
 49
while(front!=rear)
 50 
{
 51
int u=que[front++];
 52
if(front==MAXN)front=0;
 53
for(int i=head[u];i!=-1;i=edge[i].next)
 54 
{
 55
int v=edge[i].to;
 56
if(dep[v]!=-1)continue;
 57
que[rear++]=v;
 58
if(rear==MAXN)rear=0;
 59
dep[v]=dep[u]+1;
 60
++gap[dep[v]];
 61 
}
 62 
}
 63 }
 64 int SAP(int start,int end)
 65 {
 66
int res=0;
 67 
BFS(start,end);
 68
int cur[MAXN];
 69
int S[MAXN];
 70
int top=0;
 71
memcpy(cur,head,sizeof(head));
 72
int u=start;
 73
int i;
 74
while(dep[start]<n)
 75 
{
 76
if(u==end)
 77 
{
 78
int temp=INF;
 79
int inser;
 80
for(i=0;i<top;i++)
 81
if(temp>edge[S[i]].cap)
 82 
{
 83
temp=edge[S[i]].cap;
 84
inser=i;
 85 
}
 86
for(i=0;i<top;i++)
 87 
{
 88
edge[S[i]].cap-=temp;
 89
edge[S[i]^1].cap+=temp;
 90 
}
 91
res+=temp;
 92
top=inser;
 93
u=edge[S[top]].from;
 94 
}
 95
if(u!=end&&gap[dep[u]-1]==0)//出现断层，无增广路
 96
break;
 97
for(i=cur[u];i!=-1;i=edge[i].next)
 98
if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1)
 99
break;
100
if(i!=-1)
101 
{
102
cur[u]=i;
103
S[top++]=i;
104
u=edge[i].to;
105 
}
106
else
107 
{
108
int min=n;
109
for(i=head[u];i!=-1;i=edge[i].next)
110 
{
111
if(edge[i].cap==0)continue;
112
if(min>dep[edge[i].to])
113 
{
114
min=dep[edge[i].to];
115
cur[u]=i;
116 
}
117 
}
118
--gap[dep[u]];
119
dep[u]=min+1;
120
++gap[dep[u]];
121
if(u!=start)u=edge[S[--top]].from;
122 
}
123 
}
124
return res;
125 }
126 int main()
127 {
128
int T,N,f[7],D,W;
129
scanf("%d",&T);
130
n = 372;
131
int s = 370,t = 371;
132
while(T--)
133 
{
134
scanf("%d",&N);
135 
init();
136
int sum = 0;
137
for(int i = 0;i < N;i++)
138 
{
139
for(int j = 0;j < 7;j++)
140 
{
141
scanf("%d",&f[j]);
142 
}
143
scanf("%d%d",&D,&W);
144
sum += D;
145
for(int j = 0;j < 7;j++)
146 
{
147
if(f[j])
148 
{
149
for(int k = 0;k < W;k++)
150 
{
151
addedge(350 + i,k * 7 + j,1);
152 
}
153 
}
154 
}
155
addedge(s,350 + i,D);
156 
}
157
for(int j = 0;j < 350;j++)
158 
{
159
addedge(j,t,1);
160 
}
161
if(SAP(s,t) == sum)
162
printf("Yesn");
163
else
164
printf("Non");
165 
}
166 }