注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2597 石头剪刀布  

2014-01-07 23:32:45|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
以前有过这么一个题……要你求三元环个数+三元空环个数
白书上也有个题……n个点的完全图每个边有两个颜色要你求三色相同环个数

这种题一般都是补集转化,C(n,3)-不合法,而不合法的非常好算
(话说艾神有一个算法能n^1.5求出三元环,三缺一,一缺二,零缺三)

这个题也是一样……竞赛图定向后,答案是C(n,3)-sigma(C(deg[i],2))
白书上网络流那一章里讲了如何用最小费用最大流求二次函数的……所以这样子其实就已经可以做了
当然如果你想更方便些也可以化一下式子就变成sigma(deg[i]^2)了,做法一样的

S->比赛->点->T

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxm 400000
#define maxn 10010
#define maxc 110
using namespace std;
int S,T,N;
int dis[maxn],flow[maxn],pre[maxn],edge[maxn];
int map[maxc][maxc],n,pos[maxn];
int nEdge=1,to[maxm],next[maxm],remain[maxm],cost[maxm],start[maxn];
void make(int a,int b,int c,int d)
{
++nEdge,to[nEdge]=b,next[nEdge]=start[a],remain[nEdge]=c,cost[nEdge]=d,start[a]=nEdge;
++nEdge,to[nEdge]=a,next[nEdge]=start[b],remain[nEdge]=0,cost[nEdge]=-d,start[b]=nEdge;
}
void read()
{
S=++N,T=++N;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
pos[i]=++N;
for(int j=1;j<=n;++j)
make(N,T,1,j*2-1);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&map[i][j]);
if(i<j)
{
make(S,++N,1,0);
if(map[i][j]==0)
make(N,pos[i],1,0);
else if(map[i][j]==1)
make(N,pos[j],1,0);
else
make(N,pos[i],1,0),make(N,pos[j],1,0);
}
}
}
bool SPFA(int S,int T)
{
static bool use[maxn];
static int queue[maxn];
int front=0,rear=1,p;
for(int i=1;i<=N;++i)
use[i]=false,dis[i]=1<<30;
queue[rear]=S,dis[S]=0,flow[S]=1<<30;
while(front!=rear)
{
use[p=queue[front=front%N+1]]=false;
for(int i=start[p];i;i=next[i])
if(remain[i]&&dis[to[i]]>dis[p]+cost[i])
{
pre[to[i]]=p;
flow[to[i]]=min(flow[p],remain[i]);
edge[to[i]]=i;
dis[to[i]]=dis[p]+cost[i];
if(use[to[i]]==false)
use[queue[rear=rear%N+1]=to[i]]=true;
}
}
return dis[T]!=1<<30;
}
int MCMF()
{
int ans=0;
while(SPFA(S,T))
{
ans=ans+flow[T]*dis[T];
for(int i=T;i!=S;i=pre[i])
{
remain[edge[i]]-=flow[T];
remain[edge[i]^1]+=flow[T];
}
}
return ans;
}
void print()
{
printf("%d\n",n*(n-1)*(n-2)/6-(MCMF()-n*(n-1)/2)/2);
int now=pos[n];
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
{
++now;
for(int k=start[now];k;k=next[k])
if((to[k]==pos[i]||to[k]==pos[j])&&remain[k]==0)
{
if(pos[i]==to[k])
map[i][j]=0,map[j][i]=1;
else
map[i][j]=1,map[j][i]=0;
}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
printf("%d%c",map[i][j],j<n?' ':'\n');
}
int main()
{
read();
print();
return 0;
}



  评论这张
 
阅读(311)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017