BJ 集训测试9 draw

​​http://www.elijahqi.win/archives/2766​​​
爆0的一天..

题意：混合图求欧拉回路问题

求多笔画问题 问最少几笔可以覆盖整张图所有边 图是混合图 数据范围1e4边数5e4

费用流暴力增广会tle 应该使用多路增广 来加快速度 但据说不一定所有图多路增广都快

暴力：

分部分分分别采用状压或欧拉回路性质

考虑无向图欧拉回路问题 一定是点度数位奇数的会增加一条路径 注意成环的情况需要将最后答案与1取max 有向图欧拉回路计数 是直接用所有入度比出度多的差/2即可 证明可以考虑上下界网络流

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=gc();}
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
return x*f;
}
int n,m;
namespace sol1{
const int N=20;
struct node{
int y,next,id;
}data[N<<1];
int h[N],dp[1<<20],num;bool f[1<<20],flag[1<<20];
inline void insert1(int x,int y,int id){
data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].id=id;
}
inline void dfs(int x,int s){
if (flag[s]) return;flag[s]=1;
for (int i=h[x];i;i=data[i].next){
int y=data[i].y,id=data[i].id;
if (s&(1<<id)) continue;dfs(y,s|(1<<id));
}
}
inline void gao(){
for (int i=0;i<m;++i){
int x=read(),y=read(),op=read();
insert1(x,y,i);if (op) insert1(y,x,i);
}memset(dp,0x3f,sizeof(dp));dp[0]=0;int S=(1<<m)-1;
for (int i=1;i<=n;++i){
dfs(i,0);
for (int s=0;s<=S;++s) f[s]|=flag[s],flag[s]=0;
}
for (int s=0;s<=S;++s){
for (int s1=s;s1;s1=s&(s1-1)){
if (f[s1]) dp[s]=min(dp[s],dp[s^s1]+1);
}
}printf("%d\n",dp[S]);
}
}
namespace sol2{
const int N=11000;
int in[N],out[N],d[N];
inline int abs(int x){
return x<0?-x:x;
}
inline void gao(){
bool flag0=0,flag1=0;
for (int i=1;i<=m;++i){
int x=read(),y=read(),op=read();
if (op) ++d[x],++d[y],flag0=1;else ++out[x],++in[y],flag1=1;
}int ans=0;
if (!flag1){int cnt=0;
for (int i=1;i<=n;++i) cnt+=d[i]&1;
ans=max(1,cnt>>1);printf("%d\n",ans);
}if (!flag0){int cnt=0;
for (int i=1;i<=n;++i) cnt+=abs(in[i]-out[i]);ans=max(1,cnt>>1);printf("%d\n",ans);
}
}
}
int main(){
//freopen("t2.in","r",stdin);
n=read();m=read();
if(n<=18) {sol1::gao();return 0;}
sol2::gao();
return 0;
}

以上图片大概可以卡掉暴力乱搞的反例

注意仍然存在一组数据可以卡偷懒的选手比如我..即一开始定向的时候直接统计答案 最后反向的时候形成了一个欧拉回路 这样的话 答案都被减没了 但其实一个欧拉回路需要1的答案

5 5

5 3 1

2 1 1

2 1 0

5 4 1

4 5 1

正解 考虑bzoj bridges那个问题 将每个点拆点考虑入度和出度的不同 先对无向图随机定向 然后建图跑网络流 流量为1 则为这图反向 考虑度数为奇数还有偶数之间的边 如果反向就会给原图带来1的正收益 度如果恰好是1和-1 那么显然反向不会对答案造成影响 但有可能对整体的答案造成影响 所以该边仍需要建出 考虑将有影响的边费用变成1此外如果该点度数为偶数 那么说明该点连的边反向之后还有一次可以反向的机会虽然不会对答案造成贡献 跑最大费用最大流即可注意 数据中可能存在自环或者是本身就构成一个欧拉回路的情况 所以使用并查集维护连通块 最后判断的时候如果该边流量还存在说明一开始定向的时候答案已经计算 反之就要检查这个是否是一个欧拉回路

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
#define N 11000
#define M 300000
using namespace std;
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=gc();}
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
return x*f;
}
struct node{
int z,next,y,c,x;
}data[M];
int num=1,h[N],fa[N],f[N],sum,d[N],cur[N],n,m,T,in[N],b[N];
bool flag[N],edge[N];
inline void insert1(int x,int y,int z,int c){
data[++num].y=y;data[num].next=h[x];data[num].z=z;h[x]=num;data[num].c=c;data[num].x=x;
data[++num].y=x;data[num].next=h[y];data[num].z=0;h[y]=num;data[num].c=-c;data[num].x=y;
}
inline int find(int x){while(x!=fa[x]) x=fa[x]=fa[fa[x]];return x;}
inline bool spfa(){
memset(flag,0,sizeof(flag));flag[0]=1;queue<int>q;q.push(0);
memset(f,0x80,sizeof(f));f[0]=0;
while(!q.empty()){
int x=q.front();q.pop();flag[x]=0;in[x]=0;
for (int i=h[x];i;i=data[i].next){
int y=data[i].y,c=data[i].c,z=data[i].z;
if (f[x]+c>f[y]&&z){
f[y]=f[x]+c;
if(!flag[y]) flag[y]=1,q.push(y);
}
}
}return f[T]>0;
}
inline int dfs(int x,int s){
if (x==T){sum-=f[T]*s;return s;}int ss=s;in[x]=1;
for (int &i=cur[x];i;i=data[i].next){
int y=data[i].y,z=data[i].z,c=data[i].c;
if (f[x]+c==f[y]&&z&&!in[y]){
int xx=dfs(y,min(z,s));if (!xx) f[y]=-inf;
s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss;
}
}return ss-s;
}
int main(){
freopen("t2.in","r",stdin);
// freopen("t2.out","w",stdout);
n=read();m=read();T=n+1;
for (int i=1;i<=n;++i) fa[i]=i;
for (int i=1;i<=m;++i){
int x=read(),y=read(),op=read();
--d[x];++d[y];int fx=find(x),fy=find(y);if (fx!=fy) fa[fx]=fy;b[fy]=1;
if (op) insert1(y,x,1,0);
}
for (int i=1;i<=n;++i){
if (d[i]>0) {
if (d[i]>1) insert1(0,i,d[i]>>1,1);sum+=d[i];
if (d[i]&1) insert1(0,i,1,0);
}
if (d[i]<0){
if (d[i]<-1) insert1(i,T,-d[i]>>1,1);
if (d[i]&1) insert1(i,T,1,0);
}
}
int ans=0;
while(spfa()) memcpy(cur,h,sizeof(h)),ans+=dfs(0,inf);
for (int i=h[0];i;i=data[i].next){
int y=data[i].y,z=data[i].z;
if (z) b[find(y)]=0;
}
for (int i=h[T];i;i=data[i].next){
int y=data[i].y,z=data[i^1].z;if (z) b[find(y)]=0;
}
for (int i=1;i<=n;++i) if (i==fa[i]&&b[i]) ++sum;
printf("%d\n",sum);
return 0;
}