over 3 years ago

因为一个攻击处对应一个武器,所以可以用二分图来跑

怕超时用bitset

注意x部和y部数据范围不同,所以rev和b的范围不同于x部

匈牙利 :o(nm) sap:o(n2m)

dinic比较厉害……是nm1/2

这道题还有另一种做法(并查集)

将每个武器的两个属性连边,如果有环则都选,无环则不选最大的。并查集维护

详见:http://cxjyxx.me/?p=664

代码(匈牙利):

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<bitset>
#define maxx 10001
#define maxy 1000001
#define maxm 2000005
using namespace std;
bitset<1000001>b;
int next[maxm]={0},point[maxx]={0},v[maxm]={0};
int rev[maxy]={0},widen=0,n;
int readln()
{
char c=getchar();int result=0;
while(!(c<='9'&&c>='0')) c=getchar();
while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
return result;
}
void addedge(int x,int y)
{
widen++;
next[widen]=point[x];point[x]=widen;v[widen]=y;
}
bool find(int x)
{
for (int k=point[x];k!=0;k=next[k])
if (!b[v[k]])
{
b[v[k]]=1;
if (rev[v[k]]==0||find(rev[v[k]]))
{
rev[v[k]]=x;return true;
}
}
return false;
}
int main()
{
int i,x,y;
n=readln();
for (i=1;i<=n;i++)addedge(readln(),i),addedge(readln(),i);
for (i=1;i<=10000;i++)
{
b.reset();
if (!find(i)) break;
}
printf("%d\n",i-1);
}
← 【bzoj3295】【树状数组套平衡树】动态逆序对 【bzoj1009】【kmp】【矩阵】GT考试 →
 
comments powered by Disqus