M
题目大意：2012世界末日来了，科学家发现了一些星球可以转移人口，不过有的人可以在一些星球上生存有的人不行，而且每个星球都有一定的承载量，现在想知道是否所有的人都可以安全转移呢？输入：首先输入一个N和M，表示人数和星球数，接着输入N行，每行有M个01组成的数，0表示第Ni个人无法再Mj号星球上生存，1表示可以生存，最后一行是每个星球的最大承载量。
分析：刚看的时候是一道比较裸的最大流题目，只要求出来最大流是否等于总人口数就行了，不过人的数量貌似是有点多的，刚开始没有管那么多直接上了最大流，不过也果然TLE，后来借鉴了一下别人的想法，就是缩点，我们发现M的值是特别小的，最大只有10，这就意味着有很多人的状态是相同的（2^10）,所以可以把这些状态相同的人压缩到一起，这样最多也就1024个人了，大大缩减了复杂度，不过很不幸依然TLE！！！，好吧，认了，只能再去找一下sap的模板带入一下，刚开始随意找了一个模板套上，不过WA了，也不知道出了什么问题，，因为不了解SAP这东西，没办法，只能学一下SAP了，在网上找了一个很不错的演示 。其实和dinic还是挺相似的，只不过这个只做了一次的DFS是从汇点到源点进行的分层，然后寻找可行弧（也就是下面有没有可以与之相连的边），如果没有可行弧，就修改他的层号，然后就这样一直找下去，直到源点的层号大于总点数或者出现断层就可以停止了。ps.生命不息，学习不止啊。
sap演示 下载
下面是AC代码。 ======================================================================================
#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;
const int MAXN = 1110;
const int oo = 1e9+7;
struct Edge{int u, v, flow, next;}edge;
int Head, cnt;
int used, cur, Stack;
int Layer, gap, cntv;///节点的总个数
void InIt()
{
cnt = 0;
memset(Head, -1, sizeof(Head));
memset(used, 0, sizeof(used));
}
void AddEdge(int u, int v, int flow)
{
edge.u = u;
edge.v = v;
edge.flow = flow;
edge.next = Head;
Head = cnt++;
edge.u = v;
edge.v = u;
edge.flow = 0;
edge.next = Head;
Head = cnt++;
}
void BFS(int End)
{
memset(Layer, -1, sizeof(Layer));
memset(gap, 0, sizeof(gap));
queue<int> Q;
Q.push(End);
Layer = 0, gap = 1;
while(Q.size())
{
int u = Q.front();
Q.pop();
for(int j=Head; j!=-1; j=edge.next)
{
int v = edge.v;
if(Layer == -1)
{
Layer = Layer + 1;
gap]++;
Q.push(v);
}
}
}
}
int SAP(int start, int End)
{
int j, top=0, u = start, MaxFlow=0;
BFS(End);
cntv = End;
memcpy(cur, Head, sizeof(Head));
while(Layer < cntv)
{///源点的层次小于总结点数,汇点是0层
if(u == End)
{
int MinFlow = oo, location;///记录下最小流量边的位置，出栈时候用
for(j=0; j<top; j++)
{
int i = Stack;
if(MinFlow > edge.flow)
{
MinFlow = edge.flow;
location = j;
}
}
for(j=0; j<top; j++)
{///所有的边减去路径上的最小流量
int i = Stack;
edge.flow -= MinFlow;
edge.flow += MinFlow;
}
MaxFlow += MinFlow;
top = location;///退栈
u = edge].u;
}
else if(gap-1] == 0)
break;///u所在的层下面的层没有了，出现了断层，也就没有了可行弧
for(j=cur; j!=-1; j=edge.next)
{///如果u有可行弧就停止
if(Layer==Layer.v]+1 && edge.flow)
break;
}
if(j != -1)
{///找到了可行弧
cur = j;///u点的可行弧是j
Stack = j;///记录下这条边
u = edge.v;
}
else
{///没有找到可行弧，修改标号
int MinIndex = cntv;
for(j=Head; j!=-1; j=edge.next)
{///查找与u相连的最小的层是多少
if(edge.flow && MinIndex > Layer.v])
{///记录下这条可行弧,下次可以直接访问这条边
MinIndex = Layer.v];
cur = j;
}
}
gap] -= 1;///u改变层，所以u原来所在层的点数减去1
Layer = MinIndex + 1;
gap] += 1;
if(u != start)
{///返回上一层
u = edge].u;
}
}
}
return MaxFlow;
}
int main()
{
int N, M;
while(scanf("%d%d", &N, &M) != EOF)
{
int i, j, u, Ni=pow(2, M), start=Ni+M+1, End=start+1;
char ch;
InIt();
for(i=1; i<=N; i++)
{
u = 0;
for(j=1; j<=M; j++)
{
while(ch = getchar(), ch ==' ' || ch == '\n');
u = u*2 + ch-'0';
}
used++;///这种状态的人+1
}
for(i=1; i<Ni; i++)
{
if(used)
{
AddEdge(start, i, used);
}
}
for(i=1; i<=M; i++)
{
scanf("%d", &u);
AddEdge(i+Ni, End, u);
}
for(i=1; i<Ni; i++) if(used)
{///如果这种状态有人
u = i;
for(j=M; j>0; j--)
{
if(u&1)
{///最后一位是1
AddEdge(i, Ni+j, used);
}
u = u >> 1;
}
}
int MaxFlow = SAP(start, End);
if(MaxFlow == N)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
页:
[1]