• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

玩家分组(二部图dp -最小差异问题)


Recommended Posts

ContractedBlock.gif

ExpandedBlockStart.gif

从11号到nn号有nn个个体,相互之间有一定的认知关系。你的任务是把一些人分成两组,这样:

每个人都被分配到其中一个组。

每组至少有一个人。

群体中的每个人都认识同一群体中的其他成员。

在满足上述条件的基础上,要求两组成员的差值(绝对值)尽可能小。请构建一个可行的方案。

请注意,xx认识yy不一定代表yy认识XX;Xx认识yy,yy认识zz,不一定代表xx认识zz。即认知关系是单向的,不可传递的。

输入格式

输入的第一行是一个整数,代表总人数nn。

从第22行到第(n-1)(n-1)行,每行有几个不同的整数,以00结尾,第(I-1)(I-1)行有jj整数a_{i,j}a

我,j

(00除外)认识a_{i,j}a代表第二个人。

我,j。

输出格式

这个话题存在于特别法官。

如果无解,请每行输出一个字符串No solution。

如果有解,请输出两行整数,分别代表两组成员。每行第一个整数是群内人数,后面几个整数按升序代表群内成员数,数字之间用空格隔开。

输入样本

输入#1副本

2 3 5 0

1 4 5 3 0

1 2 5 0

1 2 3 0

4 3 2 1 0

输出#1副本

3 1 3 5

2 2 4

说明/提示

数据规模和一致性

确保所有测试点的2 \leq n \leq 1002n100和1 \leq a_{i,j} \leq n1a。

我,j

n .

查看问题

思考

分两组的时候,一般要考察二分图,特别是两点不能在一起的时候,一定是二分图。

如何翻译成两个不能在一起的点,这更是分题分析。

通过二分图,有很多连通的板块,每个连通的板块又可以分为两类(二分图,两类颜色用2和3表示(位运算))。

关键是DP,这里是最小化它们之间的差值,它们两个数之和是一个固定值N,

所以我们只需要看一下相连的块门,有多少种类型和数量可以组合(一组),就可以知道另一组的数量。

这相当于数据包dp,DP [j]=1表示这个号码可以连接,

想想重要:如果目前只有一个连通块,那么它的type 3就是0,这个0也可以更新,这一点尤为重要!(可以解决特殊情况!)

应该是这个背包,二维数组,可以追溯。

ContractedBlock.gif

ExpandedBlockStart.gif

#包含位/标准数据。h

使用命名空间std

#定义M 105

#定义ri寄存器int

模板类G空读(G x)

{

x=0;int f=0;char ch=getchar();

while(ch ' 0 ' | | ch ' 9 '){ f |=ch=='-';ch=getchar();}

while(ch=' 0 ' ch=' 9 '){ x=(x1)(x3)(ch^48);ch=getchar();}

x=f?-x : x;

返回;

}

int n,m;

int arr[M][M];

vector int p[M];

vector int q[M][M];

int tmp=0;

int标志[M];

int vis[M];

void dfs(int a)

{

vis[a]=1;

q[tmp][flag[a]]。push _ back(a);

for(ri I=0;ip[a]。size();我)

{

int b=p[a]

if(标志==标志[a])

{

printf(“无解”);

退出(0);

}

flag=flag[a]^1;

if(vis)继续;

外勤支助部(b);

}

}

int DP[M][M];

int pr[M][M];

int ANS1[M],ans 2[M];

int main(){

读作(n);

for(ri I=1;I=n;我)

{

while(1)

{

int a;

改为(a);if(a==0)break;

arr[a]=1;

}

}

for(ri I=1;I=n;我)

{

for(ri j=I 1;j=n;j)

{

如果(!arr[j]||!arr[j])

{

p。push _ back(j);

p[j]。push_back(一);

}

}

}

for(ri I=1;I=n;我)

{

如果(!标志)

{

tmp

flag=2;

外勤支助部;

}

}

DP[0][0]=1;

for(ri I=1;i=tmp我)

{

for(ri j=0;j=n/2;j)

{

int t=j-q[2]。size();

如果(t=0)

{

if(dp[i-1][t])dp[j]=1,pr[j]=2;

}

t=j-q[3].size();

如果(t=0)

{

if(dp[i-1][t])

{

DP[j]=1;pr[j]=3;

}

}

}

}

int ans=0:

for(ri I=n/2);i=1i -)

{

if(dp[tmp])

{

ans=i打断;打断;

}

}

int ff=ans

int cur=n/2;

for(ri I=tmp);i=1i -)

{

int a=pr[ans];

for(ri j=0);j[a ].size();(j)

{

int b=q[a][j];

年份1=1;

}

年-=q[a].size();

}

for(ri I=1);i=n(一)

{

if(ANS1)继续;

ans 2=1;

}

printf("% d,ff ");

for(ri I=1);i=n(一)

{

if(ans 1)printf(% d,I);

}

printf(" \ n ");

printf("% d,n-ff ");

for(ri I=1);i=n(一)

{

if(ans 2)printf(% d,I);

}

返回0;

}

视图代码

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now