默认分类 – 第 72 页

[ZSOI 生成树]组合数学

【题目】

Description

　　有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边，一共有 n个不同的五角形。这些五角形只在五角形圈的中心的圈上有公共的顶点。如图0所示是一个4-五角形圈。
现在给定一个n五角形圈，你的任务就是求出n五角形圈的不同生成树的数目。还记得什么是图的生成树吗？一个图的生成树是保留原图的所有顶点以及顶点的数目减去一这么多条边,从而生成的一棵树。
注意：在给定的n五角形圈中所有顶点均视为不同的顶点。

Input

输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组测试数据包含一个整数n( )，代表你需要求解的五角形圈中心的边数。

Output

对每一组测试数据，输出一行包含一个整数x，表示n五角形圈的生成树数目模2007之后的结果。

Sample Input

1
2

Sample Output

【算法分析】
把每一个五边形当成一个状态，并按顺时针进行编号。
那么第i个状态和其它状态连接的就只有在中心圈中对应的两个点。
然后我们考虑最终必然是有且仅有一个状态是中心圈对应的点并非通过该五边形连接的。
这个特殊的状态必然是去掉圈上边和剩下四条边的任意一条。所以有4种删边法。
除了这个状态以后，其它状态都是独立的，并且应当只去掉1条边。
一共五条边，所以就是有5种情况。
所以，根据乘法原理，答案应该是4*5^(n-1)。
又由于那个特殊的状态可以分步在n个状态中的任意一个，并且所得结果必然都是不同的。
所以最终结果：4*n*5^(n-1)。
【CODE】
#include #include #include const int mod=2007;
int n,ans;

void solve(){
ans=1;
for (int i=1;i ans=ans*4%mod;
ans=ans*n%mod;
printf("%dn",ans);
}

int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%d",&n);
solve();
}
}

[SPOJ412 COVER]特殊图的最小费用流巧妙优化

【题目地址】https://www.spoj.pl/problems/COVER/
【题目大意】
有n个点，m条有向边，这m条有向边的权值w=cost[x]+cost[y]，求k条边满足：
1、这k条边之间没有共起点和共终点的
2、这k条边的权和最小
【算法分析】
容易建图：
将n个点每个点拆成(i,i’)
然后对于有向边(x,y)，连边(x,y’)，该边权为cost[x]+cost[y]
于是相当于对这个二分图，求k次最小费用流的增广。
然后由于m太大，我们需要更快的算法。
对于观察每次增广，实际上就是匈牙利算法中的找交错轨，
并且新增的权总为增广路中的cost[起点]+cost[终点]
然后我们可以利用这个性质，将cost排序，然后有：当终点一样的情况下，让前面的先匹配比较好。
所以一个点只用进去一次就可以了。
最后就是每次枚举从某一点出发找增广路，找出本次增广增加的费用最小的。
然后去实现这个增广即可。
。。。罗嗦了这么多，结合程序看吧= =
【其它】
时间复杂度O(k*(n+m))
【CODE】
#include #include #include const int N=10005;
const int INF=1000000000;
struct gtp{int y,next;}g[1001111];
int n,m,k,ans,times;
int ls[N],link[N],v[N],cost[N][2],zz[N],To_y[N],cx[N];

void Read(int &x){
char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
for (x=0;ch>=’0′ && ch<='9';ch=getchar())
x=x*10+ch-‘0’;
}

int cmp(const void *x,const void *y){return ((int*)x)[0]-((int*)y)[0];}

void init(){
memset(ls,0,sizeof(ls));
memset(link,0,sizeof(link));
memset(cx,0,sizeof(cx));
Read(k); Read(n); Read(m);
for (int i=1;i<=n;i++){
Read(cost[i][0]);
cost[i][1]=i;
}
qsort(&cost[1][0],n,sizeof(int)*2,cmp);
for (int i=1;i<=n;i++) zz[cost[i][1]]=i;
for (int i=1,x,y;i<=m;i++){
Read(x); Read(y);
x=zz[x]; y=zz[y];
g[i].y=y; g[i].next=ls[x]; ls[x]=i;
}
}

int Try(int p){
int res=INF,tmp;
for (int t=ls[p];t;t=g[t].next)
if (!v[g[t].y]){
v[g[t].y]=1;
if (!link[g[t].y]) tmp=cost[g[t].y][0];
else tmp=Try(link[g[t].y]);
if (tmp res=tmp;
To_y[p]=g[t].y;
}
}
return res;
}

void expand(int p){
int q=link[To_y[p]];
link[To_y[p]]=p;
if (q) expand(q);
}

void solve(){
ans=0;
for (int i=1;i<=k;i++){
memset(v+1,0,sizeof(int)*n);
memset(To_y+1,0,sizeof(int)*n);
int now=INF,nowi,tmp;
for (times=1;times<=n;times++)
if (cx[times]==0){
tmp=cost[times][0]+Try(times);
if (tmp now=tmp;
nowi=times;
}
}
if (now==INF){
printf("NONEn");
return;
}
ans+=now;
expand(nowi);
cx[nowi]=1;
}
printf("%dn",ans);
}

int main(){
int Tc;
Read(Tc);
for (int i=1;i<=Tc;i++){
init();
solve();
}
}

[SGU174 Walls]并差集、排序+二分查找

【题目大意】
给出一些只在端点相交的线段。
问在连了第几条边之后，这些线段中的一部分连成了一个完整的封闭图形。
【算法分析】
封闭图形就是一个环，如果已经成同一连通分量的两个点再被连，就是成环了。
这个可以用并差集判断。
然后我们需要快速查找点。
由于本题都是静态的东西，所以快排+二分足矣。
如果需要动态算法可以考虑hash表和平衡树。
【其它】1A
【CODE】

#include #include #include struct Point{int x,y;}list[400005],a[200005][2];
int n,tot,f[400005];

void input(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d%d%d",&a[i][0].x,&a[i][0].y,&a[i][1].x,&a[i][1].y);
list[++tot]=a[i][0];
list[++tot]=a[i][1];
}
}

int Findst(int x){
int l=1,r=tot,mid;
while (l mid=(l+r)/2;
if (x>list[mid].x) l=mid+1;
else r=mid;
}
return l;
}

int Finded(int x){
int l=1,r=tot,mid;
while (l+1 mid=(l+r)/2;
if (x>=list[mid].x) l=mid;
else r=mid-1;
}
if (x==list[r].x) return r;
return l;
}

int Find(Point tmp){
int l=Findst(tmp.x),r=Finded(tmp.x),mid;
while (l mid=(l+r)/2;
if (tmp.y>list[mid].y) l=mid+1;
else r=mid;
}
return l;
}

int cmp(const void *x,const void *y){
if (((Point*)x)->x==((Point*)y)->x) return ((Point*)x)->y-((Point*)y)->y;
return ((Point*)x)->x-((Point*)y)->x;
}

int GF(int p){
if (f[p]==p) return p;
return f[p]=GF(f[p]);
}

void solve(){
for (int i=1;i<=tot;i++) f[i]=i;
for (int x,y,i=1;i<=n;i++){
x=Find(a[i][0]);
y=Find(a[i][1]);
if (GF(x)==GF(y)){
printf("%dn",i);
return;
}
f[f[x]]=f[y];
}
printf("0n");
}

int main(){
input();
qsort(list+1,tot,sizeof(Point),cmp);
solve();
}

[SGU206 Roads]KM算法的妙用

【题目大意】

给定N个城市和M条道路，其中前N-1条道路是大路，其它都是小路，并保证大路可构成N个城市的生成树。

第i条路费用为c_i，要求你谎报费用（设第i条路上报的费用为d_i），使得对费用数组d来说，N-1条大路恰为最小生成树，并且sum|c_i-d_i|尽可能小。

（摘自：http://crfish.blogbus.com/logs/62846336.html）

【算法分析】

本题的解题报告来自：http://wenku.baidu.com/view/7bfaa802de80d4d8d15a4faf.html

大概是这样：

令w[i]表示第i条路需要改变的量，且w[i]>=0

假设该路是大路，显然d[i]=c[i]-w[i];

假设该路是小路，显然d[i]=c[i]+w[i];

然后对于树环有限制条件：c[i]-w[i]<=c[j]+w[j] (其中i为大路，j为小路)

变形成：w[i]+w[j]>=c[i]-c[j]。

于是KM里有不等式w[i]+w[j]>=P[i,j]。

然后由于最后KM的顶标之和等于最佳匹配的总权值，而对于该题而言，这个总权又是必须的。

于是两个问题等价了。

【CODE】

#include #include #include struct gtp{int x,y,w,op,next;}g[810];
int n,m,p,dis;
int w[405][405],fa[66],depth[66],lx[405],ly[405],link[405],ls[66];
bool cx[405],cy[405];

inline void swap(int &x,int &y){x=x^y; y=x^y; x=x^y;}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].w);
g[i].next=ls[g[i].x];
ls[g[i].x]=i;
g[i].op=i+m;
}
for (int i=m+1;i<=2*m;i++){
g[i].x=g[i-m].y;
g[i].y=g[i-m].x;
g[i].w=g[i-m].w;
g[i].next=ls[g[i].x];
ls[g[i].x]=i;
g[i].op=i-m;
}
}

void buildtree(int p){
for (int t=ls[p];t;t=g[t].next)
if ((t fa[g[t].y]=t;
depth[g[t].y]=depth[p]+1;
buildtree(g[t].y);
}
}

void buildgraph(){
memset(w,0,sizeof(w));
int i,x,y,Fa;
for (i=n;i<=m;i++){
x=g[i].x; y=g[i].y;
while (y!=x){
if (depth[x]>depth[y]) swap(x,y);
Fa=fa[y];
if (Fa>=n) Fa=g[Fa].op;
w[Fa][i-n+1]=max(0,g[Fa].w-g[i].w);
y=g[fa[y]].x;
}
}
p=max(n-1,m-n+1);
}

bool find(int i){
cx[i]=true;
int q;
for (int j=1;j<=p;j++)
if (lx[i]+ly[j]==w[i][j] && !cy[j]){
cy[j]=true;
q=link[j];
link[j]=i;
if (!q || find(q)) return true;
link[j]=q;
}
else if (!cy[j]) dis=min(dis,lx[i]+ly[j]-w[i][j]);
return false;
}

void KM(){
int i,j;
for (i=1;i<=p;i++)
for (j=1;j<=p;j++)
if (w[i][j]>lx[i])
lx[i]=w[i][j];
for (i=1;i<=p;i++){
for (;;){
for (j=1;j<=p;j++) cx[j]=false;
for (j=1;j<=p;j++) cy[j]=false;
dis=0x7FFFFFFF;
if (find(i)) break;
for (j=1;j<=p;j++) if (cx[j]) lx[j]-=dis;
for (j=1;j<=p;j++) if (cy[j]) ly[j]+=dis;
}
}
}

void output(){
for (int i=1;i<=p;i++) g[i].w-=lx[i];
for (int i=1;i<=p;i++) g[i+n-1].w+=ly[i];
for (int i=1;i<=m;i++)
printf("%dn",g[i].w);
}

int main(){
input();
buildtree(1);
buildgraph();
KM();
output();
}

[HDOJ3402 Ants run!]排序

【算法分析】
排序，然后判断就可以。
对于每只蚂蚁，我们只考虑他什么时候能追上前面那只蚂蚁就可以，因为被追上与之是对应的。
所以我们要尽量让后面那只蚂蚁难追上前面那只蚂蚁。
所以我们排序即可。
【CODE】
#include #include #include #include #include using namespace std;
const double pi=3.141592653589793238462643383279502884197169399375;
int n;
int a[100005];
double r;

void input(){
scanf("%d %lf",&n,&r);
for (int i=0;i scanf("%d",&a[i]);
r=2*r*pi/n;
}

void solve(){
double ans=1e50;
for (int i=1;i if (a[i]!=a[i-1] && r/(a[i]-a[i-1]) ans=r/(a[i]-a[i-1]);
if (ans==1e50) printf("Infn");
else printf("%.3lfn",ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
input();
sort(a,a+n);
solve();
}
}