访问次数：

Wenji's blog
头部背景图片
WenJi's blog |
WenJi's blog |

生日快乐

2018-09-23
#无

无（追梦过啥生日）

风语咒

2018-09-22
#感想(杂谈)

被感动的一张图片
今天在网上看了一下国产动漫电影《风语咒》，实话看了之后。
感觉还是不错的，没想到剧情还是可以的。感觉国漫有希望了，
和之前《大鱼海棠》比，是两种不同风格的电影。这个电影的
很多特效技术，说实话也就是画风真的是国内的极致。虽然从中
可以看到很多电影的影子，但是并没有落入俗套，看了之后，
尤其对其中的感人情节记忆很深，让我也感受到这部片子想带给
我的东西。真的不错，动漫迷真的可以看下。

poj2377 最小生成树 负数化变成最大生成树 prime算法实践

2018-09-21
#prime 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define INF 1<<30
#define maxn 1010
using namespace std;
int G[maxn+1][maxn+1];
int intree[maxn];
int minweight[maxn];
int sumweight;
int flag=0;
void chushihua()
{
	memset(intree,0,sizeof(intree));
	memset(minweight,0,sizeof(minweight));
	flag=0;
	for(int i=0;i<maxn;i++)
	{
		for(int j=0;j<=maxn;j++)
		{
			G[i][j]=INF;
		}
	}
	sumweight=0;
}
void prime(int n)
{
	int node,Minweight;
	for(int i=1;i<=n;i++)
		minweight[i]=G[1][i];
	intree[1]=1;
	for(int i=2;i<=n;i++)
	{
		Minweight=INF;
		for(int j=1;j<=n;j++)
		{
			if(minweight[j]<Minweight&&!intree[j])
			{
				Minweight=minweight[j];
				node=j;
			}
		}
		intree[node]=1;
		sumweight+=Minweight;
		for(int j=1;j<=n;j++)
		{
			if(!intree[j]&&minweight[j]>G[node][j])
			{
				minweight[j]=G[node][j];
			}
		}	
	}
}
int  main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		int a1,a2,v;
		chushihua();
		for(int i=1;i<=m;i++)	
		{
			scanf("%d%d%d",&a1,&a2,&v);
			G[a1][a2]=-v;
			G[a2][a1]=-v;
		}
		prime(n);
		for(int i=1;i<=n;i++)
		{
			if(intree[i]==0)
				{flag=1;
				break;}
		}
		if(flag)
		printf("-1\n");
		else
		printf("%d\n",-sumweight);
	}
	return 0;
 }

hdu2066 Dijkstra 最短路 无向图版本 板子修改

2018-09-21
#Dijkstra 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int map[1111][1111];
int dis[1111];
int book[1111];
int maxn=1<<30;
int main()
{
	int t,s,d;
	while(cin>>t>>s>>d)
	{
	int minnn;
	for(int i=0;i<=1110;i++)
		for(int j=0;j<=1110;j++)
			if(i==j) map[i][j]=0;
			else map[i][j]=maxn;
	for(int i=1;i<=t;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		map[a][b]=min(map[a][b],c);
		map[b][a]=map[a][b];
	}
	for(int i=0;i<=1110;i++)
		book[i]=0;
	book[0]=1;
	for(int i=1;i<=s;i++)
	{
		int a;
		cin>>a;
		map[0][a]=map[a][0]=0;
	}
	for(int i=0;i<=1110;i++)
	{
		dis[i]=map[0][i];
	}
	int u;
	for(int i=1;i<=1110;i++)
	{
		minnn=maxn;
		for(int j=1;j<=1110;j++)
		{
			if(book[j]==0&&dis[j]<minnn)
			{
				minnn=dis[j];
				u=j;
			}
		}
		book[u]=1;
		for(int v=1;v<=1110;v++)
		{
				if(dis[v]>dis[u]+map[u][v]&&!book[v])
					dis[v]=dis[u]+map[u][v];
		}
	}
	int minn=maxn;
	for(int i=1;i<=d;i++)
	{
		int a;
		cin>>a;
		minn=min(dis[a],minn);
	}
	cout<<minn<<endl;}
	return 0;
}

Dijkstra 最短路 有向图版本板子 无向图就是双重附边

2018-09-21
#Dijkstra 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 #include <stdio.h>
    int main()
    {
        int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;
        int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
        //读入n和m，n表示顶点个数，m表示边的条数
        scanf("%d %d",&n,&m);

        //初始化
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i==j) e[i][j]=0;
                  else e[i][j]=inf;

        //读入边
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&t1,&t2,&t3);
            e[t1][t2]=t3;
        }
        //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
        for(i=1;i<=n;i++)
            dis[i]=e[1][i];
        //book数组初始化
        for(i=1;i<=n;i++)
            book[i]=0;
        book[1]=1;

        //Dijkstra算法核心语句
        for(i=1;i<=n-1;i++)
        {
            //找到离1号顶点最近的顶点
            min=inf;
            for(j=1;j<=n;j++)
            {
                if(book[j]==0 && dis[j]<min)
                {
                    min=dis[j];
                    u=j;
                }
            }
            book[u]=1;
            for(v=1;v<=n;v++)
            {
                if(e[u][v]<inf)
                {
                    if(dis[v]>dis[u]+e[u][v])
                        dis[v]=dis[u]+e[u][v];
                }
            }
        }

        //输出最终的结果
        for(i=1;i<=n;i++)
            printf("%d ",dis[i]);

        getchar();
        getchar();
        return 0;
    }
/*
可以输入以下数据进行验证。第一行两个整数 n m。n 表示顶点个数（顶点编号为 1~n），m 表示边的条数。接下来 m 行表示，每行有 3 个数 x y z。表示顶点 x 到顶点 y 边的权值为 z。
    6 9
    1 2 1
    1 3 12
    2 3 9
    2 4 3
    3 5 5
    4 3 4
    4 5 13
    4 6 15
    5 6 4
运行结果是
    0 1 8 4 13 17
*/

线段树板子

2018-09-21
#线段树 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int A[maxn];
struct dian
{
    int l,r;
    int d;
    int lazy;
}sum[maxn<<2];
void pushup(int rt)
{
    sum[rt].d=max(sum[rt<<1].d,sum[rt<<1|1].d);
}
void build(int l,int r,int rt)
{
    sum[rt].l=l;
    sum[rt].r=r;
    sum[rt].d=0;
    sum[rt].lazy = 0;
    if(l!=r)
    {
        int mid=(l+r)>>1;
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
    }
}
void xiachuan(int rt)
{
        sum[rt<<1].lazy+=sum[rt].lazy;
        sum[rt<<1|1].lazy+=sum[rt].lazy;
        sum[rt<<1].d+=sum[rt].lazy;
        sum[rt<<1|1].d+=sum[rt].lazy;
        sum[rt].lazy=0;
}
void cha(int l,int r,int rt)
{
    if(sum[rt].l==l&&sum[rt].r==r)
    {
        sum[rt].d++;
        sum[rt].lazy++;
        return;
    }
    if(sum[rt].lazy)
    xiachuan(rt);
    int mid=(sum[rt].l+sum[rt].r)>>1;
    if(r<=mid)
        cha(l,r,rt<<1);
    else if(l>mid)
        cha(l,r,rt<<1|1);
    else
    {
        cha(l,mid,rt<<1);
        cha(mid+1,r,rt<<1|1);
    }
    pushup(rt);
}
int query(int l,int r,int rt)
{
    if(sum[rt].l==l&&sum[rt].r==r)
        return sum[rt].d;
    if(sum[rt].lazy) 
    xiachuan(rt);
    int mid=(sum[rt].r+sum[rt].l)>>1;
    if(r<=mid)
        return query(l,r,rt<<1);
    else if(l>mid)
        return query(l,r,rt<<1|1);
    else
        return max(query(l,mid,rt<<1),query(mid+1,r,rt<<1|1));
}
int main()
{
		int k,m;
		int a,b;
		memset(A,0,sizeof(A));
        scanf("%d%d",&k,&m);
        build(1,1000000,1);
        int id=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            b--;
            if(query(a,b,1)<k)
            {
                A[id++]=i+1;
                cha(a,b,1);
            }
        }
        for(int i=0;i<id;i++)
        printf("%d ",A[i]);
    return 0;
}

contest1 hdu3635 drahonball 并查集升级版本 理解并查集基本概念和应用

2018-09-21
#并查集 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;//龙珠和城市都有区分 
int gen[10010];//龙珠附属于某个城市 
int num[10010];//龙珠移动次数 
int rankk[10010];//所在城市的龙珠数
int find(int x)
{
	int r=x;
	while(r!=gen[r])
	{
		num[r]+=num[gen[r]];
		r=gen[r];
	}
	int i=x,j;
	while(i!=r)
	{
		j=gen[i];
		gen[i]=r;
		i=j;
	}
} 
void join(int a,int b)
{
	int fx=find(a);
	int fy=find(b);
	if(fx!=fy)
	{
		gen[fx]=fy;
		rankk[fy]+=rankk[fx];
		num[fx]=1;
	}
}
int main()
{
	int N; 
	cin>>N;
	int ttt=0;
	while(N--)
	{
		int n,m;
		ttt++;
		cin>>n>>m;
		string caozuo;
		for(int i=1;i<=n;i++)
		{
			gen[i]=i;
			num[i]=0;
			rankk[i]=1;
		} 
		for(int i=1;i<=m;i++)
		{
			int a,b;
			cin>>caozuo;
			if(caozuo=="T")
			{
				cin>>a>>b;
				join(a,b);
			} 
			else
			{
				cin>>a;
				int temp=find(a);
				cout<<"Case "<<ttt<<":"<<endl<<temp<<" "<<rankk[temp]<<" "<<num[a]<<endl;
			}
		}
	}
	return 0;
}

并查集基础题hdu1232畅通工程详解附带模板

2018-09-21
#并查集 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring> 
using namespace std;
int pre[1010];
int flag[1010];//判断是否是根节点 
int find(int x)
{
	int r=x;
	while(pre[r]!=r)
	{
		r=pre[r];
	}
	int i=x;
	int j;
	while(i!=r)			//路径压缩 
	{
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;
}
void join(int x,int y)			//判断是否均为联通分支，并且进行合并 
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	{
		pre[fx]=fy;
	}
}
int main()
{
	int N,M;
	int a,b;
	int total;
	while(scanf("%d%d",&N,&M)&&N)
	{
		for(int i=1;i<=N;i++)
		{
			pre[i]=i;
		}
		for(int i=1;i<=M;i++)
		{
			
			scanf("%d%d",&a,&b);
			join(a,b);
		}
		memset(flag,0,sizeof(flag));
		for(int i=1;i<=N;i++)
		{
			int gen=find(i);
			flag[gen]=1;
		}
		total=0;
		int shu=0;//根节点的数目 
		for(int i=1;i<=N;i++)
		{
				if(flag[i])
				{
					shu++;
				} 
		}
		total=shu-1;//易错，不能写成shu--,因为运算的优先性 
		printf("%d\n",total);
	} 
	return 0;
}

contest1 rumor 并查集基础变式练习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
typedef long long ll;
using namespace std;
int pre[100010];
ll gold[100010];
int vis[100010];//判断是否是根节点 
int find(int x)
{
	int r=x;
	while(pre[r]!=r)
	{
		r=pre[r];
	}
	int i=x,j;
	while(i!=r)
	{
		j=pre[i];
		pre[i]=r;//易错，不是r=pre[i],而是pre[i]=r; 
		i=j;
	}
	return r;
}
void join(int a,int b)
{
	int fx=find(a);
	int fy=find(b);
	if(fx!=fy)
	{
			pre[fx]=fy;
	}
}
int main()
{
	int N,M;
	ll total;
	while(cin>>N>>M)
	{
	 	for(int i=1;i<=N;i++)
	 	{
	 		cin>>gold[i];//lld的输入不用scanf,而是用cin,或者是%I64d这样。 
		}
		for(int i=1;i<=N;i++)
		{
			pre[i]=i;
		} 
		for(int i=1;i<=M;i++)
		{
			int a,b;
			cin>>a>>b;
			join(a,b);
		}
		memset(vis,0,sizeof(vis)); 
		for(int i=1;i<=N;i++)
		{
			int gen=find(i);
			vis[gen]=1;
			gold[gen]=min(gold[gen],gold[i]);//本题易错，这里是一个易错点。 
		}
		total=0;
		for(int i=1;i<=N;i++)
		{
			if(vis[i])
			{
				total+=gold[i];
			}
		}
		cout<<total<<endl; 
	}
	return 0;
}

contest1 hdu1873优先队列的结构体应用题

2018-09-21
#数据结构 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
class bingren
{
public:
	int id;
	int youxianji;
	friend bool operator < (const bingren &a,const bingren &b)	//比较奇怪的一个地方，只有加上const 才可以过，也可以直接(bingren a,bingren b); 
{
	if(a.youxianji!=b.youxianji)
	return a.youxianji<b.youxianji;
	else
	return a.id>b.id;
}
};
int num=0;
int main()
{
	int N;
	while(cin>>N)
	{
		num=0;
		priority_queue<bingren> q[4];
		string s1;
		int a,b;
		while(N--)
		{
			cin>>s1;
			if(s1=="IN")
			{
				cin>>a>>b;
				bingren tt;
				num++;
				tt.youxianji=b;
				tt.id=num;
				q[a].push(tt); //队列入队时push,不是input 
			}
			else
			{
				cin>>a;
				if(!q[a].empty())
				{
					bingren tm=q[a].top();
					q[a].pop();
					cout<<tm.id<<endl;
				}
				else
				{
					cout<<"EMPTY"<<endl;
				}
			}
		}
	}
	return 0;
 }

set练习题

2018-09-21
#数据结构

丑数 优先队列和set查重count练习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;//此题易错是long long 不是int 
int main()
{
	ll n;
	int factor[3]={2,3,5};
	while(cin>>n&&n!=0)
	{
		priority_queue<ll,vector<ll>, greater<ll> > q1;
		set<ll> q2;
		q1.push(1);
		q2.insert(1);
		ll i;
		for(i=1;;i++)
		{
			ll m1=q1.top();
			q1.pop();
			if(i==n)
			{
				printf("%lld\n",m1);
				break;
			} 
			for(int j=0;j<3;j++)
			{
					ll m2=m1*factor[j];
					if(!q2.count(m2))
					{
						q1.push(m2);
						q2.insert(m2);	
					}			
			}
		
		}
	}
	return 0;
}

set对结构体排序的常见用法和排序插件cmp的用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<set>
#include<string>
#include<cstdio>
using namespace std;
struct Student
{
	int id;
	string name;
}stu1,stu2,stu3;
struct setcmp//set容器的插件,来确定set内部的排序 
{
	bool operator()(Student a,Student b)
	{
	return a.id>b.id;					//这个大括号不可以省略，不然会报错的										
	}
};
struct Setcmp
{
	bool operator()(Student a,Student b)
	{
	return a.id<b.id;	
	}
}; 
int main()
{
	set<Student,setcmp> my;
	set<Student>::iterator it; 
	stu1.id=1000;
	stu2.id=2000;
	stu3.id=3000;
	stu1.name="ddd";
	stu2.name="www";
	stu3.name="aaa";
	my.insert(stu1);
	my.insert(stu2);
	my.insert(stu3);	
	for(it=my.begin();it!=my.end();it++)
	{
		cout<<it->id<<" "<<it->name<<endl;
	}
	set<Student,Setcmp> mm;
	mm.insert(stu1);
	mm.insert(stu2);
	mm.insert(stu3);
	for(it=mm.begin();it!=mm.end();it++)
	{
		cout<<it->id<<" "<<it->name<<endl;
	}	
	return 0;
}

uva10815 set练习以及输入流sstream中的stringstream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<sstream>
#include<set>
using namespace std;
int main()
{
	set<string> str;
	string s;
	while(cin>>s)
	{
		for(int i=0;i<s.length();i++)
		{
			if(isalpha(s[i]))
			{
				s[i]=tolower(s[i]);
			}
			else
			{
				s[i]=' ';//一个字符空格时' '不是" "; 输入的非字符转换为空格，作为单词的分界点
			}
		}
		stringstream ss(s);//流 ;
		//构造时就写进，因为时对象的原因，将s加入ss流类里面,就类似于文件里面的输入文件一样 
		string s2;
		while(ss>>s2)
		{
			str.insert(s2); 
		} 
	}
	for(set<string>::iterator it=str.begin();it!=str.end();it++)
	{
		cout<<*it<<endl;
	}
	return 0;
}