ACM | 落絮飞雁的个人网站

Once there was a special graph. This graph had n vertices and some edges. Each edge was either white or black. There was no edge connecting one vertex and the vertex itself. There was no two edges connecting the same pair of vertices. It is special because the each vertex is connected to at most two black edges and at most two white edges.

One day, the demon broke this graph by copying all the vertices and in one copy of the graph, the demon only keeps all the black edges, and in the other copy of the graph, the demon keeps all the white edges. Now people only knows there are w0 vertices which are connected with no white edges, w1 vertices which are connected with 1 white edges, w2 vertices which are connected with 2 white edges, b0 vertices which are connected with no black edges, b1 vertices which are connected with 1 black edges and b2 vertices which are connected with 2 black edges.

The precious graph should be fixed to guide people, so some people started to fix it. If multiple initial states satisfy the restriction described above, print any of them.

Input

The first line of the input is a single integer T (T≤700), indicating the number of testcases.

Each of the following T lines contains w0,w1,w2,b0,b1,b2. It is guaranteed that 1≤w0,w1,w2,b0,b1,b2≤2000 and b0+b1+b2=w0+w1+w2.

It is also guaranteed that the sum of all the numbers in the input file is less than 300000.

Output

For each testcase, if there is no available solution, print −1. Otherwise, print m in the first line, indicating the total number of edges. Each of the next m lines contains three integers x,y,t, which means there is an edge colored t connecting vertices x and y. t=0 means this edge white, and t=1 means this edge is black. Please be aware that this graph has no self-loop and no multiple edges. Please make sure that 1≤x,y≤b0+b1+b2.

Sample Input

2
1 1 1 1 1 1
1 2 2 1 2 2

Sample Output

-1
6
1 5 0
4 5 0
2 4 0
1 4 1
1 3 1
2 3 1

题目大意是构造一个无向图。先考虑白色边，构造常链连接1和2即可。注意排重。

参考代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define sf scanf
int T;
int a[5],b[5];
int d[1000005];
int main()
{
    sf("%d",&T);
    while(T--)
    {
        for(int i = 0;i<3;i++)sf("%d",a+i);
        for(int i = 0;i<3;i++)sf("%d",b+i);
        int sum = 0;
        for(int i = 0;i<3;i++)sum+=a[i];
        if( (a[1]&1) || (b[1]&1) )
        {
            puts("-1");
            continue;
        }
        if(sum==4)
        {
            puts("4\n1 2 0\n1 3 0\n2 3 1\n3 4 1");
            continue;
        }
        printf("%d\n",a[1]/2+a[2]+b[1]/2+b[2]);
        int t = 1;
        while(a[2]!=-1){printf("%d %d 0\n",t,t+1);t++;a[2]--;}t++;
        while(a[1]!=2){printf("%d %d 0\n",t,t+1);t+=2;a[1]-=2;}
 
            int tt = 0;
            for(int i = 1;i<=sum;i+=2) d[tt++] = i;
            for(int i = 2;i<=sum;i+=2)d[tt++] = i;
 
        t = 0;
        while(b[2]!=-1){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t++;b[2]--;}t++;
        while(b[1]!=2){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t+=2;b[1]-=2;}
 
    }
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

#define sf scanf

int T;

int a[5],b[5];

int d[1000005];

int main()

{

sf("%d",&T);

while(T--)

{

for(int i = 0;i<3;i++)sf("%d",a+i);

for(int i = 0;i<3;i++)sf("%d",b+i);

int sum = 0;

for(int i = 0;i<3;i++)sum+=a[i];

if( (a[1]&1) || (b[1]&1) )

{

puts("-1");

continue;

}

if(sum==4)

{

puts("4\n1 2 0\n1 3 0\n2 3 1\n3 4 1");

continue;

}

printf("%d\n",a[1]/2+a[2]+b[1]/2+b[2]);

int t = 1;

while(a[2]!=-1){printf("%d %d 0\n",t,t+1);t++;a[2]--;}t++;

while(a[1]!=2){printf("%d %d 0\n",t,t+1);t+=2;a[1]-=2;}

int tt = 0;

for(int i = 1;i<=sum;i+=2) d[tt++] = i;

for(int i = 2;i<=sum;i+=2)d[tt++] = i;

t = 0;

while(b[2]!=-1){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t++;b[2]--;}t++;

while(b[1]!=2){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t+=2;b[1]-=2;}

}

Date Time

16/02/29 21:30

Author

落絮飞雁

Category

HDOJ

Tags

2 Comments

HDOJ1085:Holding Bin-Laden Captive!——母函数

Problem Description
We all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China!
“Oh, God! How terrible! ”

Don’t be so afraid, guys. Although he hides in a cave of Hang Zhou, he dares not to go out. Laden is so bored recent years that he fling himself into some math problems, and he said that if anyone can solve his problem, he will give himself up!
Ha-ha! Obviously, Laden is too proud of his intelligence! But, what is his problem?
“Given some Chinese Coins (硬币) (three kinds– 1, 2, 5), and their number is num_1, num_2 and num_5 respectively, please output the minimum value that you cannot pay with given coins.”
You, super ACMer, should solve the problem easily, and don’t forget to take $25000000 from Bush!

Input
Input contains multiple test cases. Each test case contains 3 positive integers num_1, num_2 and num_5 (0<=num_i<=1000). A test case containing 0 0 0 terminates the input and this test case is not to be processed.

Output
Output the minimum positive value that one cannot pay with given coins, one line for one case.

Sample Input
1 1 3
0 0 0

Sample Output
4

参考代码：

#include<cstdio>
#include<cstring>
#include<cmath>
int c1[1000],c2[10000];
int main()
{
	int n1,n2,n5;
	while(scanf("%d%d%d",&n1,&n2,&n5)==3,n1+n2+n5)
	{
		int n,i,j,k;
		n=n1+n2*2+n5*5;
		for(i=0;i<=n;i++)//init c1 c2
		{
			c1[i]=0;c2[i]=0;
		}
		for(i=0;i<=n1;i++)//只有 1
		{
			c1[i]=1;
		}
		for(i=0;i<=n1;i++)//存在1和2
		{
			for(j=0;j<=n2*2;j+=2)
			{
				c2[i+j]+=c1[i];
			}
		}
		for(k=0;k<=n1+n2*2;k++)
		{
			c1[k]=c2[k];c2[k]=0;
		}
		for(j=0;j<=n1+n2*2;j++)//存在1、2、5
		{
			for(k=0;k<=n5*5;k+=5)
			{
				c2[k+j]+=c1[j];
			}
		}
		for(i=0;i<=5*n5+2*n2+n1;i++)
		{
			c1[i]=c2[i];c2[i]=0;
		}
		bool flag=0;
		for(i=0;i<=n;i++)
		{
			if(c1[i]==0)
			{
				printf("%d\n",i);
				flag=1;
				break;
			}
		}
			if(!flag)
				printf("%d\n",n+1);
		}
		return 0;
	}

#include<cstdio>

#include<cstring>

#include<cmath>

int c1[1000],c2[10000];

int main()

{

int n1,n2,n5;

while(scanf("%d%d%d",&n1,&n2,&n5)==3,n1+n2+n5)

{

int n,i,j,k;

n=n1+n2*2+n5*5;

for(i=0;i<=n;i++)//init c1 c2

{

c1[i]=0;c2[i]=0;

}

for(i=0;i<=n1;i++)//只有 1

{

c1[i]=1;

}

for(i=0;i<=n1;i++)//存在1和2

{

for(j=0;j<=n2*2;j+=2)

{

c2[i+j]+=c1[i];

}

for(k=0;k<=n1+n2*2;k++)

{

c1[k]=c2[k];c2[k]=0;

}

for(j=0;j<=n1+n2*2;j++)//存在1、2、5

{

for(k=0;k<=n5*5;k+=5)

{

c2[k+j]+=c1[j];

}

for(i=0;i<=5*n5+2*n2+n1;i++)

{

c1[i]=c2[i];c2[i]=0;

}

bool flag=0;

for(i=0;i<=n;i++)

{

if(c1[i]==0)

{

printf("%d\n",i);

flag=1;

break;

}

if(!flag)

printf("%d\n",n+1);

}

return 0;

}

Date Time

16/02/27 15:59

Author

落絮飞雁

Category

HDOJ

Tags

水题

Leave a Reply

HDOJ1038:Biker’s Trip Odometer——数学题

Problem Description
Most bicycle speedometers work by using a Hall Effect sensor fastened to the front fork of the bicycle. A magnet is attached to one of the spokes on the front wheel so that it will line up with the Hall Effect switch once per revolution of the wheel. The speedometer monitors the sensor to count wheel revolutions. If the diameter of the wheel is known, the distance traveled can be easily be calculated if you know how many revolutions the wheel has made. In addition, if the time it takes to complete the revolutions is known, the average speed can also be calculated.
For this problem, you will write a program to determine the total distance traveled (in miles) and the average speed (in Miles Per Hour) given the wheel diameter, the number of revolutions and the total time of the trip. You can assume that the front wheel never leaves the ground, and there is no slipping or skidding.

Input
Input consists of multiple datasets, one per line, of the form:

diameter revolutions time

The diameter is expressed in inches as a floating point value. The revolutions is an integer value. The time is expressed in seconds as a floating point value. Input ends when the value of revolutions is 0 (zero).

Output
For each data set, print:

Trip #N: distance MPH

Of course N should be replaced by the data set number, distance by the total distance in miles (accurate to 2 decimal places) and MPH by the speed in miles per hour (accurate to 2 decimal places). Your program should not generate any output for the ending case when revolutions is 0.

Constants

For p use the value: 3.1415927.
There are 5280 feet in a mile.
There are 12 inches in a foot.
There are 60 minutes in an hour.
There are 60 seconds in a minute.
There are 201.168 meters in a furlong.

Sample Input
26 1000 5
27.25 873234 3000
26 0 1000

Sample Output
Trip #1: 1.29 928.20
Trip #2: 1179.86 1415.84

一道数学题。简单水过。注意格式即可。
代码：

#include<stdio.h>
#define Pi 3.1415927

int main()
{
	int n,c=0;
	double t,d,v,s;
	while(scanf("%lf%d%lf",&d,&n,&t)!=EOF && n!=0)
	{
		s=n*Pi*d/12/5280;
		v=s/(t/60/60);
		printf("Trip #%d: %.2lf %.2lf\n",++c,s,v);
	}
		return 0;
}

#include<stdio.h>

#define Pi 3.1415927

int main()

{

int n,c=0;

double t,d,v,s;

while(scanf("%lf%d%lf",&d,&n,&t)!=EOF && n!=0)

{

s=n*Pi*d/12/5280;

v=s/(t/60/60);

printf("Trip #%d: %.2lf %.2lf\n",++c,s,v);

}

return 0;

}

Date Time

16/01/5 15:40

Author

落絮飞雁

Category

POJ

Tags

搜索问题

2 Comments

POJ3279:Fliptile——搜索、开关问题

约翰又来折腾牛了……
READ MORE →

Date Time

15/12/28 22:34

Author

落絮飞雁

Category

POJ

Tags

3 Comments

POJ3276：Face The Right Way——开关问题、简单DP

~~牛头人~~约翰和牛的故事。
READ MORE →

Date Time

15/11/17 16:21

Author

落絮飞雁

Category

HDOJ

Tags

网络流

Leave a Reply

HDOJ1733：Escape——网络流分层图

该来的总是会来的，写一道最头痛的网络流问题。
READ MORE →