hzw神犇写的A+B问题,膜
%%%%%%
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define INF 0x7fffffff
using namespace std;
int a,b,cnt;
int ans[10],h[10],head[10],father[10],bit[10],mp[3][3],w[3],c[3],f[3];
struct data1{int to,next,v;}e[10];
struct data2{int x,y,v;}ed[10];
struct data3{int l,r,sum;}tr[10];
void insert(int u,int v,int w)
{
cnt++;
e[cnt].to=v;
e[cnt].v=w;
e[cnt].next=head[u];
head[u]=cnt;
}
bool bfs()
{
int q[10],t=0,w=1,i,now;
memset(h,-1,sizeof(h));
q[0]=h[0]=0;
while(t<w)
{
now=q[t];t++;
i=head[now];
while(i)
{
if(e[i].v&&h[e[i].to]==-1)
{q[w++]=e[i].to;h[e[i].to]=h[now]+1;}
i=e[i].next;
}
}
if(h[3]==-1)return 0;
return 1;
}
int dfs(int x,int f)
{
if(x==3)return f;
int w,used=0,i=head[x];
while(i)
{
if(e[i].v&&h[e[i].to]==h[x]+1)
{
w=f-used;
w=dfs(e[i].to,min(e[i].v,w));
e[i].v-=w;
e[i^1].v+=w;
used+=w;
if(used==f)return f;
}
i=e[i].next;
}
if(!used)h[x]=-1;
return used;
}
void dinic()
{
cnt=1;
memset(head,0,sizeof(head));
insert(0,1,a);insert(1,0,0);
insert(1,3,INF);insert(3,1,0);
insert(0,2,b);insert(2,0,0);
insert(2,3,INF);insert(3,2,0);
while(bfs()){ans[1]+=dfs(0,INF);}
}
void spfa()
{
cnt=0;
memset(head,0,sizeof(head));
insert(0,1,a);
insert(1,2,b);
int dis[3],q[10],t=0,w=1,i,now;
bool inq[10];
memset(dis,127/3,sizeof(dis));
memset(inq,0,sizeof(inq));
q[0]=dis[0]=0;inq[0]=1;
while(t<w)
{
now=q[t];t++;
i=head[now];
while(i)
{
if(e[i].v+dis[now]<dis[e[i].to])
{
dis[e[i].to]=e[i].v+dis[now];
if(!inq[e[i].to])
{
inq[e[i].to]=1;
q[w++]=e[i].to;
}
}
i=e[i].next;
}
inq[now]=0;
}
ans[2]=dis[2];
}
void floyd()
{
memset(mp,127/3,sizeof(mp));
mp[1][2]=a;mp[2][3]=b;
for(int k=1;k<=3;k++)
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
ans[3]=mp[1][3];
}
void seg_build(int k,int s,int t)
{
tr[k].l=s;tr[k].r=t;
if(s==t)return;
int mid=(s+t)>>1;
seg_build(k<<1,s,mid);
seg_build(k<<1|1,mid+1,t);
tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
}
void seg_change(int k,int x,int y)
{
int l=tr[k].l,r=tr[k].r;
tr[k].sum+=y;
if(l==r)return;
int mid=(l+r)>>1;
if(y<=mid)seg_change(k<<1,x,y);
else seg_change(k<<1|1,x,y);
}
int seg_ask(int k,int x,int y)
{
int l=tr[k].l,r=tr[k].r;
if(x==l&&y==r)return tr[k].sum;
int mid=(l+r)>>1;
if(mid>=y)return seg_ask(k<<1,x,y);
else if(mid<x)return seg_ask(k<<1|1,x,y);
else return seg_ask(k<<1,x,mid)+seg_ask(k<<1|1,mid+1,y);
}
void segtree()
{
seg_build(1,1,2);
seg_change(1,1,a);
seg_change(1,1,b);
ans[4]=seg_ask(1,1,2);
}
int lowbit(int x){return x&(-x);}
int bit_ask(int x)
{
int s=0;
while(x)
{
s+=bit[x];
x-=lowbit(x);
}
return s;
}
void bit_change(int x,int y)
{
while(x<=2)
{
bit[x]+=y;
x+=lowbit(x);
}
}
void bitree()
{
bit_change(1,a);
bit_change(2,b);
ans[5]=bit_ask(2);
}
int find(int x){return x==find(x)?x:father[x]=find(father[x]);}
bool cmp(data2 a,data2 b){return a.v<b.v;}
void kruskal()
{
ed[1].x=0;ed[1].y=1;ed[1].v=a;
ed[2].x=1;ed[2].y=2;ed[2].v=b;
sort(ed+1,ed+3,cmp);
for(int i=0;i<=2;i++)father[i]=i;
for(int i=1;i<=2;i++)
{
int x=father[ed[i].x],y=father[ed[i].y];
if(x!=y){father[x]=y;ans[6]+=ed[i].v;}
}
}
void dp()
{
w[1]=w[2]=1;
c[1]=a;c[2]=b;
for(int i=1;i<=2;i++)
for(int v=2;v>=w[i];v--)
f[v]=max(f[v],f[v-w[i]]+c[i]);
ans[7]=f[2];
}
int main()
{
scanf("%d%d",&a,&b);
dinic();//cout<<ans[1]<<endl;
spfa();//cout<<ans[2]<<endl;
floyd();//cout<<ans[3]<<endl;
segtree();//cout<<ans[4]<<endl;
bitree();//cout<<ans[5]<<endl;
kruskal();//cout<<ans[6]<<endl;
dp();//cout<<ans[7]<<endl;
for(int i=1;i<=7;i++)ans[0]+=ans[i];
ans[0]/=7;
printf("%d",ans[0]);
return 0;
}
这个方法有点多呀。。
look this!!!
哈哈哈哈哈哈哈哈哈草 是神人了orz
hh