其实就写了两道图论题，其他都不会写
[noip2014day1-T2]联合权值
题目
https://www.luogu.org/problemnew/show/P1351
题解
刚开始直接打了一个SPFA，一下过样例，感到很开心，一提交。。。。。。。30.。。。。。。。。求我此时心理阴影面积最后，找到了一种很简单的方法，即枚举每一个点，然后枚举可以连到他的点，然后对着些点直接统计答案就ok了，详细的看代码吧！
代码
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=2e6+10;
const int mod
=10007;
template<typename T
>inline void read(T
&x
)
{
x
=0;
static int f
=1;
static char ch
=getchar();
while (!isdigit(ch
)) { if (ch
=='-') f
=-1; ch
=getchar(); }
while (isdigit(ch
)) x
=(x
<<1)+(x
<<3)+(ch
^48), ch
=getchar();
x
*=f
;
}
int ver
[maxn
<<1],Next
[maxn
<<1],head
[maxn
],len
=0;
inline void add(int x
,int y
)
{
ver
[++len
]=y
,Next
[len
]=head
[x
],head
[x
]=len
;
}
int cost
[maxn
],ans(0),maxi(0);
inline void work(int x
)
{
int sum
=0,max1
=0,max2
=0;
for (int i
=head
[x
];i
;i
=Next
[i
])
{
if (cost
[ver
[i
]]>max1
)
{
max2
=max1
;
max1
=cost
[ver
[i
]];
}
else if (cost
[ver
[i
]]>max2
)
max2
=cost
[ver
[i
]];
ans
=(ans
+sum
*cost
[ver
[i
]])%mod
;
sum
=(sum
+cost
[ver
[i
]])%mod
;
}
maxi
=max(maxi
,max1
*max2
);
}
int main()
{
int n
;read(n
);
for (int i
=1;i
<n
;++i
)
{
int x
,y
;read(x
);read(y
);
add(x
,y
),add(y
,x
);
}
for (int i
=1;i
<=n
;++i
)
read(cost
[i
]);
for (int i
=1;i
<=n
;++i
)
work(i
);
printf("%d %d\n",maxi
,(ans
*2)%mod
);
return 0;
}
[noip2014day2-T2]寻找道路
题目
https://www.luogu.org/problemnew/show/P2296
题解
两道T2均是图论题，额，一看，又有最短路，果断SPFA走起，，也没想那么多，直接就码上，然后一顿改，然后全WA，，，，，，，，，，，，，，，，，我的心理阴影面积啊 好吧，看过题解后，重新写了一遍，大致思路是这样的： 首先，预处理，把每条边反向。 从终点开始bfs，标记从终点开始可以走到的点。 第二步，枚举每一个点，如果这个点没有被标记，则枚举它的每一条出边（反向后的），如果它指向的点被标记，则说明这个被标记的点不合法，删除。（当然，是假删除，否则会删掉一些不该删的点。） 第三步，在合法点上bfs，单源最短路（我就喜欢用spfa，虽然他死了。）。找到答案。
代码
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=3e5+10;
const int inf
=0x3f3f3f;
inline int read()
{
int x
=0,f
=1;
char ch
=getchar();
while (!isdigit(ch
)) { if (ch
=='-') f
=-1; ch
=getchar(); }
while (isdigit(ch
)) x
=(x
<<1)+(x
<<3)+(ch
^48), ch
=getchar();
return x
*f
;
}
int ver
[maxn
<<1],Next
[maxn
<<1],head
[maxn
],len
;
inline void add(int x
,int y
)
{
ver
[++len
]=y
,Next
[len
]=head
[x
],head
[x
]=len
;
}
int dist
[maxn
],vis
[maxn
],ok
[maxn
];
inline void spfa(int s
)
{
memset(dist
,inf
,sizeof(dist
));
memset(vis
,0,sizeof(vis
));
queue
<int>q
; q
.push(s
);
dist
[s
]=0,vis
[s
]=1;
while (!q
.empty())
{
int x
=q
.front();
q
.pop();
vis
[x
]=0;
for (int i
=head
[x
];i
;i
=Next
[i
])
{
int y
=ver
[i
];
if (dist
[y
]>dist
[x
]+1 && ok
[y
])
{
dist
[y
]=dist
[x
]+1;
if (!vis
[y
]) q
.push(y
),vis
[y
]=1;
}
}
}
}
inline void bfs(int s
)
{
memset(vis
,0,sizeof(vis
));
queue
<int>q
;
q
.push(s
);
ok
[s
]=vis
[s
]=1;
while (!q
.empty())
{
int x
=q
.front();
q
.pop();
for (int i
=head
[x
];i
;i
=Next
[i
])
if (!vis
[ver
[i
]])
q
.push(ver
[i
]),ok
[ver
[i
]]=1,vis
[ver
[i
]]=1;
}
}
int main()
{
int n
=read(),m
=read();
for (int i
=1;i
<=m
;++i
)
{
int x
=read(),y
=read();
add(y
,x
);
}
int s
=read(),t
=read();
bfs(t
);
for (int i
=1;i
<=n
;++i
)
vis
[i
]=ok
[i
];
for (int i
=1;i
<=n
;++i
)
if (!vis
[i
])
for (int j
=head
[i
];j
;j
=Next
[j
])
if (ok
[ver
[j
]])
ok
[ver
[j
]]=0;
spfa(t
);
if (dist
[s
]<=inf
)
printf("%d\n",dist
[s
]);
else
puts("-1");
return 0;
}
转载于:https://www.cnblogs.com/hsm-eternity/p/10292413.html
相关资源：NOIP2014年普及组试题 数据 解题报告
