[数据结构与算法]图论综合练习

还是整了一版这一周大致刷的题目，稍有些水了

Contest Balloons

• CodeForces - 725D

题意：
给一堆队伍，然后每个队伍有气球数和重量数，如果气球数大于重量数，这个队就会起飞（被淘汰），然后在按照气球的多少排名，我们在第一只队伍，我们可以将我们的气球分给别的队，然后问我们队的排名最高是多少。
思路：
二分答案，然后ok函数中写一个优先队列$O(n)$模拟，模拟当前比我们靠前的队伍中气球数和重量数之差最小是多少。
AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+5;
struct Team{
    ll t,w;
}t[maxn];
bool cmp(Team x,Team y){
    return x.t > y.t;
}
int n;
Team US;
priority_queue<ll, vector<ll>, greater<ll> >q;
bool ok(int x,int loc){
    // cout<<x<<"##"<<endl;
    while(!q.empty())q.pop();
    for(int i = 1; i < loc; i++){
        q.push(t[i].w - t[i].t + 1);
    }
    Team tmp = US;    
    while(1){
        if(q.size() < x)return true;
        if(tmp.t <= 0)return false;
        ll u = q.top();q.pop();
        // cout<<u<<"$$"<<endl;
        if(tmp.t < u)return false;
        tmp.t -= u;
        while(t[loc].t > tmp.t && loc < n){
            q.push(t[loc].w - t[loc].t + 1);
            loc++;
        }
    }
}
int main(){
    scanf("%d",&n);
    scanf("%lld%lld",&US.t,&US.w);
    for(int i = 1;i < n; i++){
        scanf("%lld%lld",&t[i].t,&t[i].w);
    }
    sort(t + 1,t + n,cmp);
    int loc = 1;
    while(t[loc].t > US.t)loc++;
    int l = 1 ,r = loc ;
    // cout<<loc<<endl;
    int ans = loc ;
    while(l <= r){
        int mid = (l + r)>>1;
        if(ok(mid,loc)){
            ans = min(ans,mid);
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout<<ans<<endl;
}

Find Color

• CodeForces - 40A
  不说了，简单数学题，被卡了一个特判

#include <bits/stdc++.h>
using namespace std;
double eps = 1e-15;
double make(int x,int y){
    return sqrt(x*x + y*y);
}
int main(){
    int x,y;
    scanf("%d%d",&x,&y);
    int flag = 0;
    if(x == 0||y==0){
        printf("black");
    }
    else {
        if(x < 0)flag ^= 1;
        if(y < 0)flag ^= 1;
        double dis = make(x,y);
        if(fabs(dis - int(dis)) < eps){
            printf("black");return 0;
        }
        int ans = 0;
        for(int i = 0; i < 2000;i += 2){
            if((dis > i||fabs(dis-i) < eps)&&(dis < i + 1||fabs(dis-(i + 1)) < eps)){
                ans = 1;break;
            }
        }
        if(flag == 1)ans ^= 1;
        if(ans == 0)printf("white");
        else printf("black");
    }
}

Two Fairs

• CodeForces - 1276B
  题意：
  有两个城市有展览会，然后我们问有多少对城市之间往来必须经过展览会这两座城市

思路：
如果这俩城市不是是割点，那么肯定都不必须经过
如果是割点，那么答案就是a割下来的点数乘b割下来的点数，两次从ab搜一下就ok了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
const int maxn = 5e5+5;
struct edge{
    int v ,next;
}e[maxn<<1];
int head[N],cnt = 0;
void add(int u,int v){
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
int n,m,a,b;
int dfn[N],low[N],num;
int iscut[N];
void Tarjan(int x,int fa){
    dfn[x] = low[x] = ++num;
    for(int i = head[x];~i;i=e[i].next){
        int v = e[i].v;
        if(!dfn[v]){
            Tarjan(v,x);
            low[x] = min(low[v],low[x]);   
            if(low[v] >= low[x]){
                iscut[x] = 1;
            }
        }
        else if(v != fa)low[x] = min(low[x],dfn[v]);
    }
}
int vis1[N],vis2[N];
void dfs1(int x){
    vis1[x] = 1 ;
    for(int i = head[x] ;~i;i=e[i].next){
        int v = e[i].v;
        if(vis1[v]||v==b)continue;
        dfs1(v);
    }
}
void dfs2(int x){
    vis2[x] = 1;
    for(int i = head[x];~i;i=e[i].next){
        int v = e[i].v;
        if(vis2[v]||v==a)continue;
        dfs2(v);
    }
}
void inits(){
    for(int i = 0 ;i <= n;i ++){
        head[i] = -1;
        iscut[i] = dfn[i] = low[i] = vis1[i] = vis2[i] = 0;
    }
    cnt = 0;
    num = 0;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d",&n,&m,&a,&b);
        inits();
        for(int i = 0;i < m; i++){
            int u,v;scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        Tarjan(1,-1);
        if(iscut[a]==0||iscut[b]==0){
            printf("0\n");continue;
        }
        // cout<<"DSAd"<<endl;
        dfs1(a);dfs2(b);
        ll aa = 0,bb = 0;
        for(int i = 1; i <= n;i++){
            if(vis1[i]==1&&vis2[i]==0)aa++;
            if(vis2[i]==1&&vis1[i]==0)bb++;
        }
        printf("%lld\n",(aa-1)*(bb-1));
    }

Giftbox

• POJ - 3018
  也没啥可说的，bfs就行

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 505;
const int M = 1005;
struct gift{
    int a[M];
}g[maxn];
int n,m;
bool com(gift a,gift b){
    for(int i = 0; i < m;i++){
        if(a.a[i] >= b.a[i])return false ;
    }
    return true;
}
struct edge{
    int v ,next;
}e[maxn*maxn];
int head[maxn],cnt;
void add(int u ,int v){
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
int d[maxn];
int ans = 0;
void bfs(int x){
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = head[u];~i;i=e[i].next){
            int v = e[i].v;
            if(d[v] < d[u] + 1){
                d[v] = d[u] + 1;
                q.push(v);
            }
            ans = max(ans,d[v]);
        }
    }
    // for(int i = 1;i <= n;i++){
    //     cout<<d[i]<<"##"<<endl;
    // }
}
void inits(){
    cnt = 0;
    for(int i = 0 ;i <= n;i++){
        head[i] = -1;d[i] = 0;
    }
    ans = 0;
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        inits();
        for(int i = 0 ;i <= n; i++){
            for(int j = 0; j < m; j++){
                scanf("%d",&g[i].a[j]);
            }
            sort(g[i].a,g[i].a + m);
        }
        for(int i = 0 ;i <= n; i++){
            for(int j = 0; j <= n; j++){
                if(com(g[i],g[j]))add(i,j);
            }
        }
        bfs(0);
        if(ans==0){
            printf("Please look for another gift shop!\n");
        }
        else printf("%d\n",ans);
    }
}

Popular Cows

• POJ - 2186

题意：其实每个牛会受某些牛欢迎，然后这个欢迎可以传递，为受所有牛欢迎的牛个数是多少
思路：
求一个强连分量，然后在看看那个强连通分量出度为0，如果出度为0的多余一个，那么肯定就是答案为0

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int N = 1e4+5;
const int maxn = 5e4 + 5;
struct edge{
    int v,next;
}e[maxn<<1];
int head[N],cnt;
void add(int u ,int v){
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
int dfn[N],low[N],num;
int st[N],top;
int ins[N];
int tag[N];
int sz[N];
int lis_num = 0;
void Tarjan(int x){
    dfn[x] = low[x] = ++num;
    st[++top] = x;
    ins[x] = 1; 
    for(int i = head[x];~i;i=e[i].next){
        int v = e[i].v;
        if(!dfn[v]){
            Tarjan(v);
            low[x] = min(low[x],low[v]);
        }
        else if(ins[v])low[x] = min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x]){
        int t;
        lis_num++;
        do{
            t = st[top--];
            tag[t] = lis_num;
            sz[lis_num]++;
            ins[t] = 0;
        }while(t!=x);
    }
}
struct Qu{
    int u ,v;
}qu[maxn];
int c[N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof head);
    for(int i = 0;i < m; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        qu[i].u = u;
        qu[i].v = v;
    }
    for(int i = 1;i <= n; i++){
        if(!dfn[i])Tarjan(i);
    }

    for(int i = 0;i < m; i++){
        int u = qu[i].u;int v = qu[i].v;
        if(tag[u]!=tag[v]){
            c[tag[u]]+=1;
            // cout<<"Dsada"<<endl;
        }
    }
    int flag = 0;
    for(int i = 1;i <= lis_num;i++){
        if(c[i]==0){
            if(flag > 0){
                printf("0\n");
                return 0;
            }
            flag = sz[i];
        }
    }
    printf("%d",flag);
}

Office Keys

• CodeForces - 830A

题意：
一个数轴上有一堆钥匙和一堆人，每个人拿一个钥匙，然后去某一个坐标轴位置，最少花费时间的方案是多少
思路：
一眼看着就像二分图最大匹配，突然发现是这样的我们这个人是同时走的，就相当于求一个匹配中的最大边权的边，然后这就不是板子能解决的事情了，然后我突然就想到了二分答案，然后每次的图是不一样的，就把大于答案的边舍弃，然后就过了，其中抄板子抄错了wa一发
看了题解竟然贪心和背包做的，enmmmm难过

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
const int maxk = 2e3+5;
ll a[maxn],b[maxk];
struct edge{
    int v,next;
    ll w;
}e[maxn*maxk];
int head[maxn],cnt;
void add(int u,int v,ll w){
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
const int N = maxk;
int n,m,p;
bool used[N];
int nx,ny,dis;
int dx[N],dy[N],cx[N],cy[N];
bool bfs(ll x){
    queue<int>que;
    dis = INF;
    memset(dx,-1,sizeof dx);
    memset(dy,-1,sizeof dy);
    for(int i = 1;i <= nx; i++){
        if(cx[i]==-1){
            que.push(i);
            dx[i] = 0;
        }
    }
    while(!que.empty()){
        int u = que.front();que.pop();
        if(dx[u] > dis)break;
        for(int i = head[u];~i;i=e[i].next){
            int v = e[i].v;
            ll w = e[i].w;
            if(w > x)continue;
            if(dy[v] == -1){
                dy[v] = dx[u] + 1;
                if(cy[v] == -1)dis = dy[v];
                else dx[cy[v]] = dy[v] + 1,que.push(cy[v]);
            }
        }
    }
    return dis != INF;
}
int dfs(int u,ll x){
    for(int i = head[u];~i;i=e[i].next){
        int v = e[i].v;
        ll w = e[i].w;
        if(w > x)continue;
        if(!used[v] && dy[v] == dx[u] + 1){
            used[v] = true;
            if(cy[v] != -1 && dy[v] == dis)continue;
            if(cy[v] == -1 || dfs(cy[v],x)){
                cy[v] = u;cx[u] = v;
                return 1;
            }
        }
    }
    return 0;
}
ll hopcroft_karp(ll x){
    ll res = 0;
    memset(cx,-1,sizeof cx);
    memset(cy,-1,sizeof cy);
    while(bfs(x)){
        memset(used,0,sizeof used);
        for(int i = 1;i <= nx; i++){
            if(cx[i] == -1)res  += dfs(i,x);
        }
    }
    return res;
}
bool ok(ll x){
    // printf("%lld\n",hopcroft_karp());
    if(hopcroft_karp(x) == n)return true;
    return false;
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    memset(head,-1,sizeof head);
    for(int i = 1;i <= n; i++){
        scanf("%lld",&a[i]);
    }
    for(int i = 1;i <= m; i++){
        scanf("%lld",&b[i]);
    }
    for(int i = 1;i <= n; i++){
        for(int j = 1;j <= m; j++){
            ll w = 0;
            w += abs(a[i] - b[j]);
            w += abs(b[j] - p);
            add(i,j,w);
        }
    }
    nx = n;ny = m;
    ll ans = 1e10;
    ll l = 0,r = 1e10;
    while(l <= r){
        ll mid = (l + r)>>1;
        if(ok(mid)){
            ans = min(ans,mid);
            r = mid - 1;
        }
        else l = mid + 1;
    }
    printf("%lld",ans);
}

Legal or Not

• HDU - 3342

思路：
拓排判环

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
int head[maxn],cnt;
struct edge{
    int v ,next;
}e[maxn];
void add(int u ,int v){
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
int in[maxn];
void inits(){
    memset(in,0,sizeof in);
    memset(head,-1,sizeof head);
    cnt = 0;
}
int main(){
    int n,m;
    while(1){
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)break;
        inits();
        int flag = 0;
        for(int i = 0;i < m ;i++){
            int u , v;
            scanf("%d%d",&u,&v);
            add(u,v);
            in[v]++;
            if(u==v)flag=1;
        }
        if(flag){
            printf("NO\n");continue;
        }
        queue<int>q;
        for(int i = 0 ;i < n;i++){
            if(in[i]==0)q.push(i);
        }
        int ct = 0;
        while(!q.empty()){
            int u = q.front();q.pop();
            ct++;
            for(int i = head[u];~i;i=e[i].next){
                int v = e[i].v;
                in[v]--;
                if(in[v]==0){
                    q.push(v);
                }
            }
        }
        if(ct < n)printf("NO\n");
        else printf("YES\n");

    }
}

题意：给你n个城市让你攻打，然后在问你最小的攻占时间
思路：
最短路，加拓扑序，题读假了，一直wa

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 3005;
const int maxn = 70005;
ll d[N];
struct edge{
    int v,next;
    ll w;
}e[maxn<<2];
int head[N],cnt = 0;
void add(int u,int v,ll w){
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
struct Node{
    int id ;
    ll d;
    bool operator < (const Node &x)const{
        return d > x.d;
    }
};
int vis[N];
int in[N];
int n,m;
vector<int>g[N];
void dijkstra(int x){
    priority_queue<Node> q;
    d[x] = 0;
    q.push({x,0});
    // vis[x] = 1;
    while(!q.empty()){
        Node u = q.top();
        q.pop();
        if(vis[u.id])continue;
        vis[u.id] = 1;
        for(int i = 0;i < (int)g[u.id].size();i++){
            int v = g[u.id][i];
            d[v] = max(d[u.id],d[v]);
            in[v]--;
            if(in[v]==0){
                q.push(Node{v,d[v]});
            }

        }
        for(int i = head[u.id];~i;i=e[i].next){
            int v = e[i].v;
            if(d[v] > d[u.id] + e[i].w){
                d[v] = d[u.id] + e[i].w;
                if(in[v]==0)q.push(Node{v,d[v]});
            }
        }
    }
}

void inits(){
    cnt = 0;
    for(int i = 0; i <= n; i++){
        d[i] = (1LL<<60);
        in[i] = vis[i] = 0;
        head[i] = -1;
        g[i].clear();
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        inits();
        for(int i = 0; i < m; i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        
        for(int i = 1; i <= n;i++){
            int k;
            scanf("%d",&k);
            for(int j = 0; j < k; j++){
                int v;scanf("%d",&v);
                // add(v,i,0);
                g[v].push_back(i);
                in[i] += 1;
            }
        }
        dijkstra(1);
        printf("%lld\n",d[n]);
    }
}