1.3 纳克萨玛斯（难度：★★★★☆）
1.3.1 试题
题目描述
“英雄们，天灾亡灵军团已经入侵到暴风城周围的村庄了，为了艾泽拉世界的未来，让我们携手对抗敌人吧！”先知eternized召集了联盟和部落的领袖们，准备组建一支讨伐军征战天灾亡灵的大本营“纳克萨玛斯”。
三天后，联盟首领bug和部落首领spacesheep分别带来了各自阵营中的精英部队。这批勇士一共有N人，属于不同的种族和各种职业。他们中不但有能沟通大自然的牛头人德鲁依，也有圣光保佑的圣骑士矮人，甚至还有能连通阴阳界的精灵术士。
“好吧，现在我们来挑选勇士吧。”先知首先挑选出一批勇士，然后将他们分为一个个单独的小队，其中每个小队包括M种角色，例如队长（leader）、攻击（Attack）、治疗（Cure）、防御（Tank）等，而且队中每种角色都有且仅有一个。由于每个勇士的能力不同，他们可能同时充当若干种角色，比如德鲁依，受到自然的恩惠，使他能成为一个合格的医疗师和防御者，而暗影牧师则能提供足够的攻击力和治疗力。另外，先知为了平衡各方阵营利益，联盟和部落被选上的人数相差不能超过D人。
先知当然希望能组织起来的小队越多越好。聪明的你能给出一个最优方案吗？
输入格式
第1行包含三个整数N（N≤10000）, M（0≤M≤10）, D（1≤D≤N）。
第2行到第N+1行，每行包含一个长度为M+1的“01”字串。串中第i位表示第i种角色，1表示可以充当该角色，0表示不能。最后一位表示阵营情况，1表示联盟，0表示部落。
输出格式
只有一个整数，表示能组建的小队的最大数目。
输入样例
6 3 2
1000
1000
1101
0111
0010
0010
输出样例
2
1.3.2 题目分析和算法实现
本题是一道图论题目，主要考查网络流和构造图论模型的能力。
初看题目，好像是一道搜索题目，但是一看到数据范围，发现搜索算法是无能为力的，是否可以利用贪心或者动态规划解决呢？又似乎并不能分析出问题的状态。不过如果能想到图论，就会隐约觉得有点像匹配了，因为属性只有人和能力值两种状态。但是单纯匹配又和题目要求组队数目没什么关系，因此必须另辟思路。我们可以观察到一个重要的信息，每支队伍的人数是固定的，因为每种能力都各需要一个不同的勇士来担当（比赛的时候许多选手都错误理解了这个条件，直接导致了整道题目不能正确地解决）。于是，假如总的队伍数确定了，那么需要勇士的数目也会确定，问题就转变为能不能组成这么多支队伍的可行性问题了。假如能想到这些，那么后面的思路就顺理成章地出来了。
判断能不能组成K支队伍，容易想到通过构图然后判断是否满流来决定的方法。先看一下怎样构图。忽略联盟和部落人数不超过D人的条件，可以想到的一种简单的办法，就是设立一个源点S和汇点T。对每一个勇士，从源点连一条容量为1的边；对每一种能力，连一条容量为K的边到汇点；而如果某个勇士具有某种能力，那么他们之间也连一条容量无限大的边。我们可以知道，如果能组建K支小队，则这个图必定满流。如果加上刚才忽略的条件，本能地，我们还会加上2个顶点，分别表示联盟和部落，从源点到这两点分别连一条边，然后再由这两点连边到相应的勇士那里，通过源点到联盟和部落的边的容量，就可以“控制”他们的数量关系。那么这两条边的容量是多少呢？用最笨的方法就是枚举容量，使两边容量符合这个条件。不过，这里有一个技巧，我们知道，一旦联盟和部落的总人数确定，他们的差的范围也知道，当然可以求出联盟和部落的最多人数为（KM+D）/2人，只要联盟和部落的人数不超过这个范围，显然不会出现联盟和部落之差超过D人（想想为什么）。至此，我们只需要枚举答案，然后通过求最普通的最大流来判断是否能达到这个答案，就能解决这个问题了。
不过回过头来看，这样做复杂度其实并不低，保守估计有N+M+4个点，超过N条边，用简单的Ford-Fulkerson或Edmonds-Karp算法，复杂度为O（Answer*N3），显然太大了。但是，我们又可以发现，虽然N很大，但是勇士们的种类只有2M种（想想为什么），于是可以压缩这个图，有效地减少节点数为2M，就是说最多也就1000来个点（210）。可以想象一下，复杂度变小了很多。具体的压缩方法其实已经很明显了，给出的勇士的状态不都是一个01串吗？将这个二进制串看做一个整数，那么每个勇士就唯一对应0…2M−1里面的一个数了。我们将这些数当做节点取代原来的勇士。从联盟（部落）节点连到这个数的边的容量为这个类型的勇士的数目。数节点和能力的连接方法和之前完全类似。这样，即使勇士再多，我们也可以轻松应付了。
但是可以看出，复杂度还是有些高，为O（Answer*23M），最大的数据会有比较大的运算量。当然，我们枚举的时候一般也会直觉地使用二分来获得答案，不过其实还能更快一点。这里有一个技巧，就是利用可增广路的性质，为算法提速。因为通常的最大流算法都是不断地增广图的流量来达到最大流的，算法的复杂度的一个决定性因数就是增广的次数（不过比赛的时候有选手采用二分+dicnic全通过数据了，但是dicnic方法还是比较麻烦的）。当答案比较大的时候，往往要将整个图进行完整地增广log（N/M）次。但实际上，我们尽可以最简单地枚举答案，每一次都在前面的流量图上求增广路，而不必每次都重新计算流量。如此下来，算法复杂度就变成O（22M*N/M）。在通常情况下能很好地解决这个问题。
1.3.3 参考程序及程序分析
#include ＜algorithm＞
#include ＜vector＞
using namespace std;
const int maxn=11000; //最大人数
const int S=1024; //源
const int T=1025; //汇
const int AH=1026; //AH部落，AH+1联盟
const int types=1028; //types+i，表示第i种角色组合
int kind[1024][2]; //二进制表示的角色组合数量统计，分0部落，1联盟
int n,m,D,ans;
vector＜int＞ G[1040]; //邻接表存储
int c[1040][1040],f[1040][1040]; //容量和流量
int mrk[1040],d[1040],list[1040],pnt[1040];
//读入数据
void readdata()
{
int i,j,k;
char s[20];
scanf("%d%d%d",&n,&m,&D);
//统计不同角色的组合数量，分开联盟和部落，存在kind数组中
memset(kind,0,sizeof(kind));
for (i=0;i＜n;++i)
{
scanf("%s",s);
k=0; //转化01串为十进制数
for (j=0;j＜m;++j)
if (s[j]=='0') k=k＊2;
else k=k＊2+1;
if (s[m]=='0') ++kind[k][0]; //统计不同类型的勇士数量
else ++kind[k][1]; //仅仅为了方便后面构图∶)
}
}
//构图
void generateG()
{
int i,j,k;
memset(c,0,sizeof(c));
for (k=0;k＜2;++k)
{
j=0;
//枚举每一种能力的组合
for (i=(1＜＜m)-1;i＞=0;--i)
if (kind[i][k]＞0)
{
//假如某一类角色组合存在，则往图中加边
G[AH+k].push_back(i); //由联盟或部落节点到i有一条边
c[AH+k][i]=kind[i][k]; //容量为kind[i][k]
G[i].push_back(AH+k);
j+=kind[i][k];
}
//添加源和汇的边
G[S].push_back(AH+k); //由源到联盟或部落节点加一条边
G[AH+k].push_back(S);
}
for (i=(1＜＜m)-1;i＞=0;--i)
if (kind[i][0]+kind[i][1]＞0)
{
j=i;
//枚举角色组合的二进制表示i中有哪些有效角色
for (k=m-1;k＞=0;--k)
{
if (j%2==1)
{
G[i].push_back(types+k); //从角色组合i连一条边到角色k
c[i][types+k]=maxn; //容量为maxn
G[types+k].push_back(i);
}
j/=2;
}
}
//往汇添加边
for (i=0;i＜m;++i)
{
G[types+i].push_back(T);
G[T].push_back(types+i);
}
}
//仅仅是简单的最大流增广，广度扩展实现
//通过Edmonds-Karp算法证明了有稳定的复杂度为O(VE∧2)，具体原理和实现参考相关书籍
int maxflow()
{
int cur,tail,i,j,u,v,flow=0;
vector＜int＞∶∶iterator ptr;
memset(pnt,0,sizeof(pnt));
//循环增广可行流
do
{
memset(mrk,0,sizeof(mrk));
memset(d,0,sizeof(d));
list[0]=S;
mrk[S]=true;
d[S]=maxn;
pnt[S]=S;
//广搜出一条增广路出来
for (cur=tail=0;cur＜=tail&&!mrk[T];++cur)
for (u=list[cur],ptr=G[u].begin();ptr!=G[u].end();++ptr)
{
v=(＊ptr);
if (!mrk[v]&&f[u][v]＜c[u][v])
{
mrk[v]=true;
list[++tail]=v;
pnt[v]=u;
if (d[u]＜c[u][v]-f[u][v]) d[v]=d[u];
else d[v]=c[u][v]-f[u][v];
}
}
//假如增广路不存在，则退出循环
if (!mrk[T]) break;
//沿着增广路对网络进行增广
flow+=d[T];
for (u=T;u!=S;)
{
v=u;
u=pnt[v];
f[u][v]+=d[T];
f[v][u]=-f[u][v];
}
} while (d[T]＞0);
//返回最大流，即从源流出的所有流量之和
return flow;
}
//枚举答案
int check()
{
int i,j,k;
for (i=0;i＜m;++i)
c[types+i][T]=ans;
c[S][AH]=(ans＊m+D)/2;
c[S][AH+1]=(ans＊m+D)/2;
maxflow();
//假如从源流出的流量满容，即表示ans组的方案可满足
return (f[S][AH]+f[S][AH+1]==m＊ans);
}
int main()
{
freopen("naxx.in","r",stdin);
freopen("naxx.out","w",stdout);
readdata(); //读入数据
generateG(); //生成图G
for (ans=1;check();++ans); //枚举并检测答案
printf("%d\n",ans-1);
return 0;
}
1.3.4 部分测试数据和输出结果
测试数据
20 3 3
0000
1011
1001
0010
0000
1001
0111
1011
0101
0001
0000
0001
1001
0110
0010
0000
1010
1001
1000
0000
输出结果
3