题面
题意
给出一张无向图,现在要对上面的边进行染色(可以认为有无数种颜色),并且每种边只能染一种颜色,每种颜色最多只能染两条边,并且与每个点相连的边最多只有k种颜色,请输出一种方案。
做法
首先如果存在一个度数大于
2
k
2k
2k的点,肯定无解,而对于度数小于等于
k
k
k的点,则无论其周围的边如何染色,都不会超过
k
k
k个颜色,因此我们只要考虑度数在
k
+
1
k+1
k+1与
2
k
2k
2k之间的点即可。 可以发现,对于度数为
i
(
k
<
i
<
=
2
k
)
i(k<i<=2k)
i(k<i<=2k)的点,在其周围的
i
i
i条边中必然有
i
−
k
i-k
i−k对边的颜色相同,我们称这些边为特殊边,则特殊边总是成对出现,且每对特殊边只能出现在一个点的旁边,因此这题可以转化为一个匹配问题,一个度数为
i
i
i点要与
m
a
x
(
2
∗
(
i
−
k
)
,
0
)
max(2*(i-k),0)
max(2∗(i−k),0)条与它相连的边匹配,可以用最大流求解,判断最大流是否与源点的出度相等即可。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define N 1210
#define M 100100
using namespace std
;
int T
,m
,n
,k
,s
,t
,bb
,first
[N
],ds
[N
],cur
[N
],deep
[N
],a
[N
],b
[N
],an
[N
],ss
,ts
,ans
,tt
;
struct Bn
{
int to
,next
,quan
;
}bn
[M
];
vector
<int>son
[N
];
queue
<int>que
;
inline void add(int u
,int v
,int w
)
{
bb
++;
bn
[bb
].to
=v
;
bn
[bb
].next
=first
[u
];
bn
[bb
].quan
=w
;
first
[u
]=bb
;
}
inline void ad(int u
,int v
,int w
)
{
add(u
,v
,w
);
add(v
,u
,0);
}
inline bool bfs()
{
int p
,q
;
memset(deep
,0,sizeof(deep
));
deep
[s
]=1;
que
.push(s
);
for(;!que
.empty();)
{
q
=que
.front();
que
.pop();
for(p
=first
[q
];p
!=-1;p
=bn
[p
].next
)
{
if(deep
[bn
[p
].to
] || !bn
[p
].quan
) continue;
deep
[bn
[p
].to
]=deep
[q
]+1;
que
.push(bn
[p
].to
);
}
}
return deep
[t
];
}
int dfs(int now
,int mn
)
{
if(now
==t
) return mn
;
int res
;
for(int &p
=cur
[now
];p
!=-1;p
=bn
[p
].next
)
{
if(!bn
[p
].quan
|| deep
[bn
[p
].to
]!=deep
[now
]+1) continue;
res
=dfs(bn
[p
].to
,min(bn
[p
].quan
,mn
));
if(res
)
{
bn
[p
].quan
-=res
;
bn
[p
^1].quan
+=res
;
return res
;
}
}
return 0;
}
int main()
{
int i
,j
,p
,q
,o
,tmp
;
cin
>>T
;
while(T
--)
{
bb
=1,ss
=ts
=0;
memset(ds
,0,sizeof(ds
));
memset(first
,-1,sizeof(first
));
memset(an
,0,sizeof(an
));
scanf("%d%d%d",&n
,&m
,&k
);
s
=0,t
=m
+n
+1;
for(i
=1;i
<=m
;i
++)
{
scanf("%d%d",&p
,&q
);
ad(p
+m
,i
,1);
ad(q
+m
,i
,1);
ds
[p
]++,ds
[q
]++;
}
for(i
=1;i
<=m
;i
++) ad(i
,t
,1),ts
++;
for(i
=1;i
<=n
;i
++)
{
if(ds
[i
]>k
)
ad(s
,i
+m
,(ds
[i
]-k
)*2),ss
+=(ds
[i
]-k
)*2;
}
if(i
<=n
|| ss
>ts
)
{
for(i
=1;i
<=m
;i
++) printf("0 ");
puts("");
continue;
}
ans
=tt
=0;
for(;bfs();)
{
for(i
=0;i
<=t
;i
++) cur
[i
]=first
[i
];
for(p
=dfs(s
,INF
);p
;ans
+=p
,p
=dfs(s
,INF
));
}
if(ans
<ss
)
{
for(i
=1;i
<=m
;i
++) printf("0 ");
puts("");
continue;
}
for(i
=1;i
<=n
;i
++) son
[i
].clear();
for(i
=1;i
<=m
;i
++)
{
for(p
=first
[i
];p
!=-1;p
=bn
[p
].next
)
{
if(bn
[p
].to
>m
&&bn
[p
].to
<=m
+n
&&bn
[p
].quan
)
{
son
[bn
[p
].to
-m
].push_back(i
);
break;
}
}
}
for(i
=1;i
<=n
;i
++)
{
for(j
=0;j
<son
[i
].size();j
+=2)
{
an
[son
[i
][j
]]=an
[son
[i
][j
+1]]=++tt
;
}
}
for(i
=1;i
<=m
;i
++)
{
if(an
[i
]) printf("%d ",an
[i
]);
else printf("%d ",++tt
);
}
puts("");
}
}