2017暑期集训Day 1

最短路与2-SAT

ref:http://blog.csdn.net/jarjingx/article/details/8521690

ref:http://www.cnblogs.com/shadowland/p/5872257.html

T1:洪水

Code:

#include<iostream> 
#include<cstdio> 
#include<cstdlib> 
#include<cstring> 
#include<queue> 
#include<algorithm> 
#define mkp(x,y) make_pair(x,y) 
#define inf 707406378 
inline int in(){ 
    int x=0;bool f=0; char c; 
    for (;(c=getchar())<'0'||c>'9';f=c=='-'); 
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0'); 
    return f?-x:x; 
} 
using namespace std; 
int t[52][52],vis[52][52]; 
bool mp[52][52]; 
char ch[52]; 
int n,m,sx,sy,ex,ey; 
typedef pair<int,int> P; 
const int dx[4]={-1,0,1,0}; 
const int dy[4]={0,1,0,-1}; 
queue <P> q,q1; 
inline bool exbound(int x,int y){ 
    return (x<0)||(x>=n)||(y<0)||(y>=m); 
} 
void bfs1(){ 
    while (!q.empty()){ 
        P p=q.front();q.pop(); 
        for (int i=0;i<4;++i){ 
            int curx=p.first+dx[i],cury=p.second+dy[i]; 
            if (exbound(curx,cury)||mp[curx][cury]) continue; 
            if ((curx==ex&&cury==ey)||t[curx][cury]!=inf) continue; 
            t[curx][cury]=t[p.first][p.second]+1;q.push(mkp(curx,cury)); 
        } 
    } 
} 
void bfs2(){ 
    memset(vis,127/3,sizeof(vis)); 
    q1.push(mkp(sx,sy));vis[sx][sy]=0; 
    while (!q1.empty()){ 
        P p=q1.front();q1.pop(); 
        for (int i=0;i<4;++i){ 
            int curx=p.first+dx[i],cury=p.second+dy[i]; 
            if (exbound(curx,cury)||mp[curx][cury]||vis[curx][cury]!=inf) continue; 
            if (vis[p.first][p.second]+1>=t[curx][cury]) continue; 
            vis[curx][cury]=vis[p.first][p.second]+1; 
            if (curx==ex&&cury==ey) {printf("%d",vis[ex][ey]);return;} 
            q1.push(mkp(curx,cury)); 
        } 
    }printf("-1"); 
} 
int main() 
{ 
    n=in();m=in();memset(t,127/3,sizeof(t)); 
    memset(mp,0,sizeof(mp)); 
    for (int i=0;i<n;++i){ 
        scanf("%s",ch); 
        for (int j=0;j<m;++j){ 
            if (ch[j]=='D') ex=i,ey=j; 
            if (ch[j]=='S') sx=i,sy=j; 
            if (ch[j]=='X') mp[i][j]=1; 
            if (ch[j]=='*') q.push(mkp(i,j)),t[i][j]=0; 
        } 
    }bfs1();bfs2(); 
    return 0; 
}

T2:Toll!Revisited!(uva_10537)

Code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#include<iostream>
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
struct edge{
    int to,next;
}e[2750];
int head[127],pre[127];
ll dis[127];
int cnt=0,p,s,t,n,cs=0;
char ch;
typedef pair<ll,int> P;
inline void ins(int x,int y){
    e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
}
inline ll ct(int u){
    if (u>='a'&&u<='z') return 1ll*(dis[u]+1);
    if (u>='A'&&u<='Z') return 1ll*(dis[u]%19?dis[u]/19*20+1+dis[u]%19:dis[u]/19*20);
}
void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P> >q;
    memset(dis,127/3,sizeof(dis));dis[s]=1ll*p;q.push(mp(1ll*p,s));
    while (!q.empty()){
        P p=q.top();q.pop();int x=p.second;
        if (dis[x]<p.first) continue;
        for (int i=head[x];i;i=e[i].next){
            int v=e[i].to;ll val=ct(x);
            if (dis[v]>val) dis[v]=val,pre[v]=x,q.push(mp(dis[v],v));
        }
    }
}
int main()
{
    while (~scanf("%d",&n)&&n!=-1){
        ++cs;memset(e,0,sizeof(e));memset(pre,0,sizeof(pre));memset(head,0,sizeof(head));cnt=0;
        for (int i=1;i<=n;++i){
            ch=getchar();while (ch<'A'||(ch>'Z'&&ch<'a')||ch>'z') ch=getchar();s=ch;
            ch=getchar();while (ch<'A'||(ch>'Z'&&ch<'a')||ch>'z') ch=getchar();t=ch;
            ins(s,t);ins(t,s);
        }p=in();
        ch=getchar();while (ch<'A'||(ch>'Z'&&ch<'a')||ch>'z') ch=getchar();s=ch;
        ch=getchar();while (ch<'A'||(ch>'Z'&&ch<'a')||ch>'z') ch=getchar();t=ch;
        dijkstra(t);printf("Case %d:
%lld
%c",cs,dis[s],s);
        for (int i=pre[s];i;i=pre[i]) printf("-%c",i);printf("
");
    }return 0;
}

T4:astronauts(LA_3713)

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mst(a,n) memset(a,n,sizeof(a))
#define MN 100005
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
struct edge{
    int to,next;
}e[MN<<2];
int head[MN<<1],st[MN<<1],w[MN];
int cnt=0,top=0,sum=0,n,m,a,b;
bool vis[MN<<1],sen[MN];
inline void ins(int x,int y){
    e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
}
bool dfs(int x){
    if (vis[x^1]) return 0;if (vis[x]) return 1;
    vis[x]=1;st[++top]=x;
    for (int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if (!dfs(v)) return 0;
    }return 1;
} 
bool twosat(){
    for (int i=2;i<(n<<1)+2;i+=2)
    if (!vis[i]&&!vis[i^1]){
        top=0;if (!dfs(i)){
            while (top) vis[st[top]]=0,--top;
            if (!dfs(i+1)) return 0;
        }
    }return 1;
}
int main()//note: a a<<1 (not a) a<<1|1
{
    while (scanf("%d%d",&n,&m)&&n&&m){
        mst(w,0);mst(sen,0);mst(e,0);
        mst(st,0);mst(head,0);mst(vis,0);cnt=sum=top=0;
        for (int i=1;i<=n;++i) w[i]=in(),sum+=w[i];
        for (int i=1;i<=n;++i) sen[i]=(w[i]*n>=sum);
        for (int i=1;i<=m;++i){
            a=in();b=in();
            if (sen[a]^sen[b]) {ins(a<<1|1,b<<1);ins(b<<1|1,a<<1);}
            else {
                ins(a<<1|1,b<<1);ins(a<<1,b<<1|1);
                ins(b<<1|1,a<<1);ins(b<<1,a<<1|1);
            }
        }if (!twosat()) {printf("No solution.
");continue;};
        for (int i=1;i<=n;++i) {
            if (vis[i<<1]) printf("%c
",sen[i]?'A':'B');
            else printf("C
");
        }
    }
    return 0;
}

T5:Priest John’s Busiest Day(poj_3683)

Code: