2014寒假总结 1.16-1.17

【1.16】

连通性状压复习
「bsoj2842」 独立插头

【1.17】

最小树形图:朱刘算法

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int INF=~0U>>2;

int N, K, Cnt;
int Ans=0;
int C[50+7], M[50+7];
struct Edge {
    int u, v, w;
} E[10000+7];

void Init()
{
    double t;
    int a, b;
    scanf("%d", &N);
    for (int i=1; i<=N; i++)
    {
        scanf("%lf %d", &t, M+i+1);
        C[i+1]=t*10;
    // printf("%d\n", C[i+1]*M[i+1]);
     if (M[i+1]) E[++Cnt]=(Edge){1, i+1, C[i+1]*M[i+1]};
        else E[++Cnt]=(Edge){1, i+1, 0};
    }
    scanf("%d", &K);
    for (int i=1; i<=K; i++)
    {
        scanf("%d %d %lf", &a, &b, &t);
        a++; b++; t*=10;
        if (!M[b]||!M[a]) continue;
        E[++Cnt]=(Edge){a, b, t*M[b]};
    }
}

int Vis[77], Pre[77];
int Id[77], In[77];

void PigCowA()
{
    int NV=++N, NE=Cnt, Root=1;
    static int k=0;
    for (;3+1-2+7;)
    {
        // printf("%d=>%d\n",++k,Ans);
     for (int i=1; i<=NV; i++) In[i]=INF;
        for (int i=1; i<=NE; i++)
        {
            if (In[E[i].v]>E[i].w&&E[i].u!=E[i].v)
            {
                In[E[i].v]=E[i].w;
                Pre[E[i].v]=E[i].u;
            }
        }
        for (int i=1; i<=NV; i++)
        {
            if (i==Root) continue;
            if (In[i]==INF) return;
        }
        int Cnt=0;
        memset(Id, -1, sizeof Id);
        memset(Vis, -1, sizeof Vis);
        In[Root]=0;
        for (int i=1, u, v; i<=NV; i++)
        {
            Ans+=In[i];
            for (v=i; Vis[v]!=i&&v!=Root&&Id[v]==-1; v=Pre[v])   
                Vis[v]=i;
            if (v!=Root&&Id[v]==-1)
                for (Id[v]=++Cnt, u=Pre[v]; u!=v; u=Pre[u]) Id[u]=Cnt;
        }
        if (!Cnt) break;
        for (int i=1; i<=NV; i++)
            if (Id[i]==-1) Id[i]=++Cnt;
        for (int i=1, v; i<=NE; i++)
        {
            v=E[i].v;
            E[i].u=Id[E[i].u];
            E[i].v=Id[E[i].v];
            E[i].w-=In[v];
        }
        NV=Cnt;
        Root=Id[Root];
    }
}

void Work()
{
    PigCowA();
    printf("%.2lf\n", Ans*1./10.);
}

int main()
{
    Init();
    Work();
    return 0;
}

最小度限制生成树:Kruskal+贪心

#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cstdio>
#include <algorithm>

int N, M, K;

int rg_n, sg_n;
struct rawedge {
    int u, v, w;
    bool operator<(const rawedge& B) const
    {
        return this->w<B.w;
    }
} rg[100000+7], sg[50000+7];

int Head[100000+7];
int Cnt=1;
struct Edge {
    int v, w, erase, nxt;
} E[100000];

void Addarc(int u, int v, int w)
{
    E[++Cnt]=(Edge){v, w, 0, Head[u]};
    Head[u]=Cnt;
    E[++Cnt]=(Edge){u, w, 0, Head[v]};
    Head[v]=Cnt;
}

int need[10000+7];
int trans[10000+7];

int max_len, max_id;
void DFS(int node, int fa, int curmax, int curid)
{
    const static int Dx=0;
// printf("%d %d %d\n",node,fa,curmax);
 if (need[node])
    {
        max_len=curmax;
        max_id=curid;
        throw Dx;
    }
    for (int p=Head[node]; p; p=E[p].nxt)
    {
        if (!E[p].erase&&E[p].v!=fa)
        {
            if (curmax<E[p].w) DFS(E[p].v, node, E[p].w, p);
            else DFS(E[p].v, node, curmax, curid);
        }
    }
}

int Fa[10000+7];
int Find(int X){return X==Fa[X]?X:Fa[X]=Find(Fa[X]);}

void Init()
{
    scanf("%d %d", &N, &M);
    for (int i=1; i<=M; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if (a>b) a^=b, b^=a, a^=b;
        if (a==1) sg[++sg_n]=(rawedge){a, b, c};
        else rg[++rg_n]=(rawedge){a, b, c};
    }
    scanf("%d", &K);
}

int Ans=0;

void Work()
{
    int a, b, c;
    for (int i=1; i<=N; i++)
        Fa[i]=i;
        
    std::sort(sg+1, sg+sg_n+1);
    std::sort(rg+1, rg+rg_n+1);
    
    for (int i=1; i<=rg_n; i++)
    {
        if ((a=Find(rg[i].u))!=(b=Find(rg[i].v)))
        {
            Fa[a]=b;
            Ans+=rg[i].w;
            Addarc(rg[i].u, rg[i].v, rg[i].w);
        }
    }
    int leaf=0, del=0;
    for (int i=1; i<=N; i++) leaf+=Find(i)==i;
    for (int i=1; i<=sg_n; i++)
    {
        if (!trans[a=Find(sg[i].v)])
        {
            trans[a]=1;
            need[sg[i].v]=1;
            
            Ans+=sg[i].w;
            leaf--;
            del++;
        }
    }
    if (leaf>1||del>K) {puts("Sorry They Can't Get Luneng Bashu Middle School"); return;}
    leaf=del;
    for (int i=1; i<=K-leaf; i++)
    {
        int maxx=0, ch=0, id;
        for (int j=1; j<=sg_n; j++)
        {
            if (!need[sg[j].v])
            {
                try{
                    DFS(sg[j].v, 0, 0, 0); // trick for quickly quiting
             }catch(...){}  
            
                if (sg[j].w-max_len<maxx) 
                    ch=j, maxx=sg[j].w-max_len, id=max_id;
            }
        }
        if (maxx>=0) break;
        
        E[id].erase=1;
        E[id^1].erase=1;
        Ans+=maxx;
        need[sg[ch].v]=1;
// printf("%d->%d %d\n",Ans,max_id,ch);
 }
    printf("Total miles driven: %d\n", Ans);
}

int main()
{
    Init();
    Work();
    return 0;
}

混合图欧拉回路:任意定向+iSAP

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

int Head[2000+7];
int Cnt=1;
int N, M, S, T;
struct Edge {
    int v, flow, nxt;
} E[20000+7];

struct raw {
    int u, v, type;
} Raw[20000+7];

void Addarc(int u, int v, int flow)
{
    E[++Cnt]=(Edge){v, flow, Head[u]};
    Head[u]=Cnt;
    E[++Cnt]=(Edge){u, 0, Head[v]};
    Head[v]=Cnt;
}

int Dis[4000+7];
int Gap[4000+7];

int SAP(int node, int flow)
{
    if (node==T) return flow;
    int sum=0;
    for (int p=Head[node]; p; p=E[p].nxt)
    {
        if (E[p].flow&&(Dis[E[p].v]+1==Dis[node]))
        {
            int dlt=SAP(E[p].v, std::min(flow, E[p].flow));
            E[p].flow-=dlt;
            E[p^1].flow+=dlt;
            sum+=dlt;
            flow-=dlt;
            if (!flow || Dis[S]==T) return sum;
        }
    }
    if (--Gap[Dis[node]]==0) Dis[S]=T;
    else ++Gap[++Dis[node]];
    return sum;
}

int Deg[2000+7];
int Deg2[2000+7];

int main()
{
    int Test, Ans=0, Indeed=0;
    scanf("%d", &Test);
    for (; Test--; )
    {
        memset(Deg, 0, sizeof Deg);
        memset(Deg2, 0, sizeof Deg2);
        memset(Head, 0, sizeof Head);
        Cnt=1; Ans=Indeed=0;
        scanf("%d %d", &N, &M);
        int a, b, c;
        for (int i=1; i<=M; i++)
        {
            scanf("%d %d %d", &Raw[i].u, &Raw[i].v, &Raw[i].type);
            a=Raw[i].u;
            b=Raw[i].v;
            Deg[a]--; // 出- 
         Deg[b]++;
        }
        int nosolution=0;
        for (int i=1; i<=N; i++)
            if ((Deg[i]+1000)%2) {nosolution=1; break;}                                
        if (nosolution) {puts("impossible"); continue;}
        S=N+1; T=S+1;
    
        for (int i=1; i<=N; i++)
        {
            if (Deg[i]<0)
                Addarc(S, i, -Deg[i]/2),
                Indeed+=-Deg[i]/2;
            if (Deg[i]>0)
                Addarc(i, T, Deg[i]/2);
        }
        for (int i=1; i<=M; i++)
        {
            if (!Raw[i].type)
            {
                Addarc(Raw[i].u, Raw[i].v, 1);
            }
        }
        memset(Dis, 0, sizeof Dis);
        memset(Gap, 0, sizeof Gap);
        Gap[0]=T;
        for (; Dis[S]<T; ) Ans+=SAP(S, 0x7fffffff/2);
        puts(Ans==Indeed?"possible":"impossible");
    }
    return 0;
}