## 今天下午图论dfs训练赛,5/10,待补，复习了最短路和最小生成树
>早上又是一个偷懒的早上
| 题目 |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
| 做题情况 |
未做 |
未做 |
AC(-3) |
AC |
未做 |
未做 |
WA(-11) |
AC(-1) |
AC(-2) |
AC(-5) |
题意是n个点,m条路,有一条未知的路在维修,求1到n最短路径的最大值。一开始以为是求最长路径，我是个读假题的机器人。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<string>
#define inf 0x3f3f3f3f
#define mem(k,b) memset(k,b,sizeof(k))
using namespace std;
const int maxn=1100;
int mp[maxn][maxn],dis[maxn],vis[maxn];
int l,m,n,x,y,w;
int pos[maxn];
void dj(int ss){
for(int i=1;i<=n;i++){
vis[i]=0,dis[i]=inf;
}
dis[1]=0;
for(int i=1;i<=n;i++){
int minn=inf;int k=-1;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]<minn){
minn=dis[j];
k=j;
}
}
if(minn==inf){
return ;
}
vis[k]=1;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[k]+mp[k][j]<dis[j]){
dis[j]=dis[k]+mp[k][j];
if(ss){pos[j]=k;}
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m)){
mem(pos,0);mem(mp,inf);
for(int i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&w);
if(mp[x][y]>w){
mp[x][y]=mp[y][x]=w;
}
}
dj(1);
int maxcost=dis[n];
for(int i=n;i!=1;i=pos[i]){
int t=mp[i][pos[i]];
mp[i][pos[i]]=mp[pos[i]][i]=inf;
dj(0);
maxcost=max(maxcost,dis[n]);
mp[i][pos[i]]=mp[pos[i]][i]=t;
}
printf("%d
",maxcost);
}
return 0;
}
一道简单的dfs题，做了好像有三四遍了，所以代码就咕咕咕。
因为不知道要干嘛，所以最后贴了一个网上的代码。说起来这道题不知道是我理解错了，还是……
反正不懂，感觉题目很奇怪，可能是自己还很菜。
读完题，这是道简单的dp，写完一wa，行吧，天天读假题，后来发现就是板子题。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 1000000007
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int maxn=1e5+10;
int g[110][110],a[110],vis[110];
int n;
int prime(int cur){
int kk, sum = 0;
rep(i, 1, n){
a[i] = g[cur][i];
vis[i] = false;
}
vis[cur] = true;
rep(i, 2, n){
int mincost = inf;
rep(j, 1, n){
if (!vis[j] && a[j] < mincost){
kk = j;
mincost = a[j];
}
}
vis[kk] = true;
sum += mincost;
rep(j, 1, n){
if (!vis[j] && a[j] > g[kk][j]){
a[j] = g[kk][j];
}
}
}
return sum;
}
int main()
{
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&g[i][j]);
}
}
printf("%d
",prime(n));
}
return 0;
}
一开始以为是八皇后问题，然后发现其实就是填充问题，还必须填满。上来裸了一个dfs超时……
然后优化过程中不能出现棋子数量大于n-剩余列数的剪枝
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 1000000007
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int maxn=10;
char g[maxn][maxn];
int vis[maxn][maxn],xx[maxn],yy[maxn];
int n,m,maxx,sum;
void dfs(int sum,int r)
{
if(!sum){
maxx++;
return;
}
for(int i=r;i<n;i++){
if(!xx[i] && n>=(sum+i)){
for(int j=0;j<n;j++){
if(!yy[j]){
if(g[i][j]=='#'&& !vis[i][j]){
yy[j]=1;xx[i]=1;vis[i][j]=1;
dfs(sum-1,r+1);
yy[j]=0;xx[i]=0;vis[i][j]=0;
}
}
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m)){
if(n==-1 && m==-1){break;}
for(int i=0;i<n;i++){
scanf("%s",g[i]);
xx[i]=0,yy[i]=0;
}
mem(vis,0);
maxx=0;
dfs(m,0);
printf("%d
",maxx);
}
return 0;
}
读完这题我终于明白我应该好好学中文和英语。
一wa这个大妈要走最短的路从1n~
二wa这个大妈可能是要1到（2n）之间最长的路~
最终在wa了四次之后，毅然决然打开百度翻译，哦，原来就是一道最小生成树，这位大妈有个瓶子，每走一米喝一口水，每个点可以把瓶子装满，要瓶子最大能装大妈几口水。
求最短路中的子路径最大即可，写完自信一wa……哦原来x和y写反了，这种细节要注意
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 1000000007
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int maxn=2100;
int g[maxn][maxn],a[maxn],vis[maxn];
int n,m;
int prime(int cur){
int kk, maxx = -1;
rep(i, 1, n){
a[i] = g[cur][i];
vis[i] = false;
}
vis[cur] = true;
rep(i, 2, n){
int mincost = inf;
rep(j, 1, n){
if (!vis[j] && a[j] < mincost){
kk = j;
mincost = a[j];
}
}
vis[kk] = true;
if(maxx<mincost){
maxx=mincost;
}
rep(j, 1, n){
if (!vis[j] && a[j] > g[kk][j]){
a[j] = g[kk][j];
}
}
}
return maxx;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
g[i][j]=0;
}
else{
g[i][j]=inf;
}
}
}
for(int i=0;i<m;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
if(g[x][y]>w){
g[x][y]=g[y][x]=w;
}
}
printf("%d
",prime(1));
}
return 0;
}
ps:一定要补题，A题看过好难……E题听王韬韬说是dp，我一定会补的 咕咕咕
记录第一次写博客的我！
#######补题 B题
终于了解到这东西原来叫链式前向星，顺便学了一手spsa算法
因为读不懂题，只能读代码找了一个好点的代码，然后开始研究……就是个笨比题，但题意很坑。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = 100100;
int head[maxn], cnt, n, m;
int vis[maxn], d[maxn];
bool w[500][500];
struct node{
int u, v, next;
}Node[maxn<<1];
inline void add(int u, int v){
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].next = head[u];
head[u] = cnt++;
}
void spfa(int s){
queue<int> Q;
for(int i=0; i<=n; i++) d[i] = INF;
mem(vis, 0);
Q.push(s);
vis[s] = 1;
d[s] = 0;
while(!Q.empty()){
int u = Q.front(); Q.pop();
vis[u] = 0;
for(int i=head[u]; i!=-1; i=Node[i].next){
node e = Node[i];
if(d[e.v] > d[u] + 1){
d[e.v] = d[u] + 1;
if(!vis[e.v]){
vis[e.v] = 1;
Q.push(e.v);
}
}
}
}
}
int main()
{
mem(head, -1);
cnt = 0;
scanf("%d%d",&n,&m);
int u, v, flag = 0;
for(int i=0; i<m; i++){
scanf("%d%d", &u, &v);
if(u == 1 && v == n || u == n && v == 1)
flag = 1;
w[u][v] = w[v][u] = 1;
add(u, v);add(v,u);
}
if(flag){
mem(head, -1);
cnt = 0;
for(int i=1; i<=n; i++){
for(int j=i+1; j<=n; j++){
if(!w[i][j])
add(i, j);add(j,i);
}
}
}
spfa(1);
if(d[n] == INF)
{
printf("-1
");
return 0;
}
printf("%d
",d[n]);
return 0;
}
等待变强更新
|