3130: [Sdoi2013]费用流

2013年4月16日 14:16

http://www.lydsy.com/JudgeOnline/problem.php?id=3130

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391645 Liu_Ts 3130 Accepted 864 kb 76 ms C++ 1934 B 2013-04-16 14:07:23

 

题意

一个图(有重边,无自环),给定一个整数P

第一问:求1到N最大流。

第二问:Alice确定一种最大流的方案,Bob给一些边分配费用,各边的单位费用和为P;求在Bob采取最优策略的情况下,Alice如何确定最大流方案,能使得最后总费用最小。

题解

显然Bob的最优策略就是把当前流量最大的一条边加上费用P;

所以Alice就要使最大流量最小。

二分答案,要注意这题因为有重边所以答案可能为实数!

 

#include<cmath>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
const int N=201,M=2010,T=1001;
const double eps=1e-6;

int u[M],v[M],next[M],head[N];
int cur[N],d[N],vd[N],pre[N];
int n,m,p,x[T],y[T],k;
double l,r,low[N],w[M],z[T];


void add(int x,int y,double z)
{
	u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
	u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}

void rebuild(double v)
{
	memset(head,0,sizeof(head));k=1;
	for(int i=1;i<=m;i++)
		add(x[i],y[i],min(v,z[i]));
}
double solve(int s,int t,double x)
{
	rebuild(x);
	memset(d,0,sizeof(d));
	memset(vd,0,sizeof(vd));
	memset(low,0,sizeof(low));
	memset(cur,0,sizeof(cur));
	int now=s,i;double ans=0;
	low[s]=INT_MAX;vd[0]=t;
	while(d[s]<t)
	{
		for(i=head[now];i;i=next[i])
			if(w[i]>0 && d[now]==d[v[i]]+1)
				break;
		cur[now]=i;
		if(i)
		{
			pre[v[i]]=i;low[v[i]]=min(low[now],w[i]);
			now=v[i];
			if(now==t)
			{
				for(;now!=s;now=u[pre[now]])
					w[pre[now]]-=low[t],w[pre[now]^1]+=low[t];
				low[s]=INT_MAX;ans+=low[t];
			}
		}
		else
		{
			if(!--vd[d[now]]) break;
			d[now]=t;
			for(i=head[now];i;i=next[i])
				if(w[i]>0 && d[now]>d[v[i]]+1)
					d[now]=d[v[i]]+1,cur[now]=i;
			vd[d[now]]++;
			if(now!=s) now=u[pre[now]];
		}
	}
	return ans;
}




int main()
{
	scanf("%d%d%d",&n,&m,&p);
	l=r=1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%lf",&x[i],&y[i],&z[i]);
		r=max(r,z[i]);
	}
	double maxflow=solve(1,n,r);
	printf("%.0lf\n",maxflow);
	int ans=0;
	while(r-l>=eps)
	{
		double mid=(l+r)/2,flow=solve(1,n,mid);
		if(maxflow-flow<=eps) r=mid-eps;
		else l=mid+eps;
	}
	printf("%.4lf\n",l*p);
}

Tags: bzoj SDOI
评论(0) 阅读(1828)

3107: [cqoi2013]二进制a+b

2013年4月16日 12:05

http://www.lydsy.com/JudgeOnline/problem.php?id=3107

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391549 Liu_Ts 3107 Accepted 1272 kb 64 ms C++/Edit 1466 B 2013-04-16 11:59:41

 

题意

给三个数a,b,c。

构造三个新二进制数A,B,C,要求每个数与原数中1的个数相同,且满足A+B=C。

求满足条件的最小的C

题解

DP,f[t][i][j][k][p],表示枚举到第t位,A已放i个1,B已放j个1,C已放k个1,若p=0,表示该状态无进位;否则表示有进位。

 

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
const int N=31;
int n,a,b,c,f[2][N][N][N][2];
inline int get(int x)
{
	int s;
	for(s=0;x;x>>=1)
		if(x&1) s++;
	return s;
}
void init()
{

	int x,y,z;scanf("%d%d%d",&x,&y,&z);
	a=get(x);b=get(y);c=get(z);
	x=max(x,max(y,z));
	for(n=0;x;x>>=1) n++;
}

void work(int &a,int b)
{
	if(a==-1) a=b;
	else a=min(a,b);
}

int main()
{
	init();
	memset(f,-1,sizeof(f));
	f[0][0][0][0][0]=0;
	int cur=0;
	for(int t=0;t<n;t++,cur^=1)
		for(int i=0;i<=min(t,a);i++)
			for(int j=0;j<=min(t,b);j++)
				for(int k=0;k<=min(t,c);k++)
				{
					if(f[cur][i][j][k][0]!=-1)
					{
						int now=f[cur][i][j][k][0];
						work(f[cur^1][i][j][k][0],now);
						if(i+1<=a&&k+1<=c) work(f[cur^1][i+1][j][k+1][0],now+(1<<t));
						if(i+1<=a&&j+1<=b) work(f[cur^1][i+1][j+1][k][1],now);
						if(j+1<=b&&k+1<=c) work(f[cur^1][i][j+1][k+1][0],now+(1<<t));
					}
					if(f[cur][i][j][k][1]!=-1)
					{
						int now=f[cur][i][j][k][1];
						work(f[cur^1][i][j][k+1][0],now+(1<<t));
						if(i+1<=a) work(f[cur^1][i+1][j][k][1],now);
						if(j+1<=b) work(f[cur^1][i][j+1][k][1],now);
						if(i+1<=a&&j+1<=b&&k+1<=c)  work(f[cur^1][i+1][j+1][k+1][1],now+(1<<t));
					}
				}				
	printf("%d\n",f[cur][a][b][c][0]);
}

Tags: bzoj CQOI
评论(0) 阅读(1627)

3108: [cqoi2013]图的逆变换

2013年4月16日 10:54

http://www.lydsy.com/JudgeOnline/problem.php?id=3108

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391508 Liu_Ts 3108 Accepted 892 kb 412 ms C++ 730 B 2013-04-16 10:40:15

 

题意

原图中的一条边为新图中的一个点,原图中两条相接的边为新图中的一条边,即a→b为点ab,a→b→c为ab→bc。

题目要求根据新图判断是否存在一个原图。

题解

如果在新图中存在 i->k 和 j->k

那么在原图里一定是这样的

所以我们可以发现,如果存在i->k和j->k

但只存在i->t或j->t其中之一,则新图不合法。

O(N^3)验证

 

#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=301;
int n,m;bool a[N][N];

inline void init()
{
	memset(a,0,sizeof(a));
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=0;i<m;i++)
		scanf("%d%d",&x,&y),a[x][y]=1;
}

inline bool check()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			bool f1=0,f2=0;
			for(int k=0;k<n;k++)
			{
				if(a[i][k]&&a[j][k]) f1=true;
				if(a[i][k]!=a[j][k]) f2=true;
				if(f1&&f2) return 0;
			}
		}
	return 1;
}

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		init();
		if(check()) puts("Yes");
		else puts("No");
	}
}

Tags: bzoj CQOI
评论(0) 阅读(2180)

3122: [Sdoi2013]随机数生成器

2013年4月15日 19:51

http://www.lydsy.com/JudgeOnline/problem.php?id=3122

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391145 Liu_Ts 3122 Accepted 9100 kb 1488 ms C++ 2158 B 2013-04-15 17:39:23

 

题意

已知Xi+1=(aXi + b)mod p;

给定X1,a,b,p(质数),t

求第一个满足Xn=t的n

题解

把原式化开,得

Xn=[a^(n-1)*X1+b*(a^(n-2)+a^(n-3)+..+a^0)]mod p;

分情况讨论

①X1=t时,ans=1;

②a=0时,

    1.b=t时,ans=2;

    2.b!=t时,ans=-1;

③a=1时,

    Xn=[X1+b*(n-1)]mod p=t

    移向之后,相当于求xb+yp=(t-X1)mod p;

    扩展gcd,ans=x+1;

④a>1时,

    Xn=[a^(n-1)*X1+b*(a^(n-1)-1)/(a-1)]mod p

    设c=(a-1)在模p意义下的逆元,即c=(a-1)^(p-2);

    Xn=[a^(n-1)*X1+bc*(a^(n-1)-1)]mod p

    化简得Xn=[(X1+bc)*a^(n-1)-bc]mod p=t

    令q=X1+bc,t`=(t+bc)mod p,

    移向后相当于求[q*a^(n-1)]mod p=t'

    接下来我的做法是,先求xq+yp=t'的解x;

    问题变为求a^x` mod p=x,ans=x`+1。就和山东11年的计算器那题一样了。

 

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<climits>
using namespace std;
typedef long long ll;
const int H=1000001;
int f[H],r[H];
ll p,a,b,x1,x,y,t;
 
ll km(ll a,ll k)
{
    if(!a) return 0;
    ll t=a,q=1;
    while(k)
    {
        if(k&1) q=((q%p)*(t%p))%p;
        t=((t%p)*(t%p))%p;
        k=k>>1;
    }
    return q;
}
void gcd(ll a,ll b,ll c)
{
    if(!b)
        if(!(c%a))
        {
            x=c/a;y=0;
            return;
        }
        else
        {
            x=-1;return;
        }
    gcd(b,a%b,c);
    if(x==-1) return;
    ll t=y;y=x-((a/b)*y);x=t;
}
       
void work1()
{
    t=(t-x1+p)%p;
    x=y=0;
    gcd(b,p,t);
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
        x++;
    }
    printf("%lld\n",x);
}
void work2()
{
    ll c=km(a-1,p-2);
    t=(t+((b*c)%p))%p;
    ll q=(x1+((b*c)%p))%p;
    x=y=0;
    gcd(q,p,t);
    if(x==-1)
    {
        puts("-1");return;
    }
    if(x!=-1)
    {
        x%=p;
        while(x<0)x+=p;
    }
    int m=int(floor(sqrt(p)+1)),b=km(a,p-1-m);;
    memset(f,255,sizeof(f));
    memset(r,255,sizeof(r));
    ll now=1;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1) h=(h+1)%H;
        f[h]=now;r[h]=i;now=now*a%p;
    }
    now=x%p;
    for(int i=0;i<m;i++)
    {
        int h=now%H;
        while(f[h]!=-1)
        {
            if(f[h]==now)
            {
                printf("%d\n",i*m+r[h]+1);
                return;
            }
            h=(h+1)%H;
        }
        now=now*b%p;
    }
    puts("-1");
}
 
void work()
{
    if(x1==t){puts("1");return;}
    if(a==0)
    {
        if(b==t) puts("2");
        else puts("-1");
        return;
    } 
    if(a==1)
    {
        work1();
        return;
    }
    work2();
}
     
int main()
{
    int T;scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
        work();
    }
}

Tags: SDOI bzoj
评论(1) 阅读(1683)

3124: [Sdoi2013]直径

2013年4月15日 16:39

http://www.lydsy.com/JudgeOnline/problem.php?id=3124

RunID User Problem Result Memory Time Language Code_Length Submit_Time
391083 Liu_Ts 3124 Accepted 14000 kb 1572 ms C++ 1383 B 2013-04-15 16:26:40

 

题意

一棵树,求直径和有多少条边一定在直径上。

题解

我就不说我省选有多傻叉了。

首先DFS求出直径,

显然一定在直径上的边一定是任意一条直径上连续的一段。

所以我们遍历求出的直径(红色+蓝色)上的每个点x,

如果以这个点为起点,在不访问直径上的点的情况下,

求出一条最长链,图中的黑色

如果等于蓝色的长度或红色的长度,那么这段蓝色或红色就不是一定在直径上。

这样不断缩小左右端点,剩下的链上的边就是答案

 

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200011,M=N*2;
int v[M],w[M],next[M],head[N],k=1;
long long d[N],dep[N],ans1,tmp;
int n,pre[N],A,B,leaf;bool vis[N];

void add(int x,int y,int z)
{
	v[++k]=y;w[k]=z;next[k]=head[x];head[x]=k;
	v[++k]=x;w[k]=z;next[k]=head[y];head[y]=k;
}

void dfs(int x,int fa)
{
	pre[x]=fa;
	if(dep[x]>tmp)
		tmp=dep[x],leaf=x;
	for(int i=head[x];i;i=next[i])
		if(v[i]!=fa)
			dep[v[i]]=dep[x]+w[i],dfs(v[i],x);
}

void  find(int x,int fa)
{
	tmp=max(tmp,d[x]);
	for(int i=head[x];i;i=next[i])
		if((v[i]!=fa) && (!vis[v[i]]))
			d[v[i]]=d[x]+w[i],find(v[i],x);
}

int main()
{
	scanf("%d",&n);int x,y,z;
	for(int i=1;i<n;i++)
		scanf("%d%d%d",&x,&y,&z),add(x,y,z);
	tmp=dep[1]=0;dfs(1,0);A=leaf;
	tmp=dep[A]=0;dfs(A,0);B=leaf;
	ans1=tmp;
	printf("%lld\n",ans1);
	memset(vis,0,sizeof(vis));
	for(int i=B;i;i=pre[i]) vis[i]=1;
	bool flag=1;int left=A,right=B;
	for(int i=B;i;i=pre[i])
	{
		long long ldist=dep[i],rdist=ans1-dep[i];
		tmp=d[i]=0;find(i,0);
		if((tmp==ldist) && flag) 
			left=i,flag=0;
		if(tmp==rdist) right=i;
	}
	int ans2=0;
	for(int i=right;i!=left;i=pre[i]) ans2++;
	printf("%d\n",ans2);
}

Tags: SDOI bzoj
评论(0) 阅读(1677)