Zadanie

Za mestom vznikol nový aquapark. Hore na kopci sú štartovacie stanovištia a dole sú veľké bazény. Zo stanovíšť do bazénov vedú tobogany, na ktorých sa radostne šmýkajú deti. Občas, keď sa plavčík nepozerá, deti skúšajú všelijaké vylomeniny, spúšťajú sa dolu hlavou, po trojiciach, alebo brzdia, keď nemajú. Inokedy ani plavčík nepomôže, niektoré deti robia hlúposti len vtedy, keď ich plavčík vidí lebo je to vraj viac cool a väčšia pocta.

Samozrejme, keď deti skúšajú nezbedy, stávajú sa úrazy a to nerobí aquaparku dobrú povesť. Prevádzkovatelia aquaparku by radi vedeli, aká je celková bezpečnosť aquaparku počas jednej sezóny.

Na každé stanovisko a ku každému bazénu môžme aj nemusíme posadiť plavčíka. Rozloženie plavčíkov sa každú chvíľu mení, až sa postupne vystriedajú úplne všetky možnosti. Bezpečnosť jedného toboganu závisí len od toho, či na jeho hornom a dolnom konci sedí plavčík. Bezpečnosť aquaparku v konkrétnom okamihu je súčin bezpečností všetkých toboganov v tom okamihu.

Úloha

Máte zadaný bipartitný graf,1 ktorý predstavuje náš aquapark. Hrany tohto grafu sú tobogany. Vrcholy tohto grafu sú bazény a štartovacie stanovištia a každý vrchol ofarbíme jednou z dvoch farieb – čiernou, ak vo vrchole sedí plavčík, a bielou, ak nesedí. Počet vrcholov označíme \(n\) a počet hrán \(m\).

Pre každú hranu \(e\) vedúcu medzi vrcholmi \(u_e\) a \(v_e\) poznáme 4 hodnoty \(b_{e00}\), \(b_{e01}\), \(b_{e10}\) a \(b_{e11}\), ktoré určujú, aká je bezpečnosť príslušnej hany podľa farieb jej koncových vrcholov.

  • \(b_{e00}\) je bezpečnosť hrany \(e\), ak sú oba vrcholy \(u_e\), \(v_e\) biele.
  • \(b_{e01}\) je bezpečnosť hrany \(e\), ak je vrchol \(u_e\) biely a \(v_e\) čierny.
  • \(b_{e10}\) je bezpečnosť hrany \(e\), ak je vrchol \(u_e\) čierny a \(v_e\) biely.
  • \(b_{e11}\) je bezpečnosť hrany \(e\), ak sú oba vrcholy \(u_e\), \(v_e\) čierne.

Všimnite si, že nehovoríme nič o tom, ktorý z vrcholov \(u\), \(v\) je začiatok toboganu a ktorý koniec.

Pozrime sa na všetkých \(2^n\) ofarbení grafu (pre všetky možnosti ako rozmiestniť plavčíkov) a pre každé ofarbenie vypočítajme súčin bezpečností všetkých \(m\) hrán. Keď tieto súčiny sčítame, dostaneme celkovú bezpečnosť aquaparku počas sezóny.

Vypočítajte túto celkovú bezpečnosť modulo \(10^9+7\).

Formát vstupu

Na prvom riadku vstupu sú čísla \(n\) a \(m\), (\(2\leq n\leq 40\), \(1\leq m\leq 100\)). Vrcholy očíslujeme postupne \(1\)\(n\).

Nasleduje \(m\) riadkov a na každom je \(6\) čísel \(u_e\), \(v_e\), \(b_{e00}\),\(b_{e01}\),\(b_{e10}\),\(b_{e11}\) popisujúcich jednu hranu (\(1\leq u_e,v_e\leq n\), \(0\leq b_{eij}\leq 10^9\)).

Čiastočné body sa budú dať získať aj za riešenia, ktoré zvládajú len malé \(n,m\), prípadne malé hodnoty \(b\). Budú aj vstupy, v ktorých je celková bezpečnosť pomerne malá.

Formát výstupu

Vypíšte jedno celé číslo – celkovú bezpečnosť lunaparku počas sezóny modulo \(1\,000\,000\,007\).

Príklady

Input:

2 1
1 2 1 2 3 4

Output:

10

Input:

3 2
1 2 1 0 0 1
2 3 1 0 0 1

Output:

2

  1. To je taký graf, ktorého vrcholy sa dajú rozdeliť na dve časti (partície) tak, aby v rámci jednej časti neviedli žiadne hrany. V našom prípadne jednu partíciu tvoria štarty toboganov a druhú partíciu bazény. Tobogan vždy vedie medzi bazénom a stanovišťom. Tiež sa dá všimnúť, že bipartitné grafy sú práve tie grafy, ktoré neobsahujú cykly nepárnej dĺžky.

Ľahko by sme napísali program, ktorý by vyskúšal všetky možné ofarbenia (tých je \(2^n\)), pre každé ofarbenie by sme len cyklom prešli hrany, vynásobili bezpečnosti a na konci to celé sčítali.

Tento algoritmus by bol príliš pomalý, pretože \(2^{40}\) je dosť veľa (približne tisíc miliárd) a to ešte treba zakaždým prechádzať hrany.

To, čo by sme však zvládli je skúšať \(2^{20}\) možností, to je predsa len milión. Ale čoho je najviac \(n/2\)? No predsa vrcholov v menšej polovici vrcholov1.

Dôležitá informácia v zadaní bola, že graf je bipartitný. To znamená, že jeho vrcholy sa dajú rozdeliť do dvoch množín \(A\), \(B\) tak, aby medzi žiadnymi vrcholmi v \(A\) neviedla hrana a tiež medzi žiadnymi vrcholmi v \(B\) neviedla hrana (hrany teda idú len z \(A\) do \(B\) a naopak). Tieto množiny voláme partície.

Tým pádom vrcholy v jednej partícii (napríklad v \(B\)) sú navzájom nezávislé. Keď zmeníme farbu vrchola \(x\) z \(B\), tak to nijako neovplyvní bezpečnosti hrán, ani súčiny bezpečností pri iných vrcholoch z \(B\).

Predstavme si, že nejako zafixujeme farby všetkých vrcholov v \(A\), napríklad nech sú všetky biele. Potom sa môžeme zaujímať, aká je čiastočná odpoveď pre takéto ofarbenia, teda súčet celkových bezpečností, pre ktoré sú všetky vrcholy z \(A\) biele. Toto číslo označíme \(G(B)\). Keby sme z grafu zahodili všetky vrcholy z partície \(B\) aj s ich hranami a nechali len jeden vrchol \(x\), mohli by sme nazvať čiastočnú odpoveď pre tento vrchol \(G({x})\).

Túto hodnotu vieme vypočítať pomerne ľahko, buď je \(x\) biely (vtedy dostaneme nejaký súčin hodnôt hrán \(w_{xb}\)), alebo je \(x\) čierny (a dostaneme súčin \(w_{xc}\)). \(G({x}) = w_{xb} + w_{xc}\).

Po úvahách o nezávislosti zistíme, že \(G(B) = G({x_1})\cdot G({x_2})\cdot \ldots \cdot G({x_b})\), teda súčin čiastkových hodnôt pre všetky vrcholy z \(B\). Môžete si aj sami rozmyslieť, prečo je to tak.

Tým pádom, pre jedno konkrétne ofarbenie \(A\) vieme rýchlym prechodom cez všetky vrcholy \(B\) zistiť \(G(B)\) pre dané \(A\). Tieto hodnoty stačí sčítať pre všetky možné ofarbenia množiny \(A\).

Pred týmto počítaním ešte musíme rozdeliť graf na partície a nezabudnúť pomenovať \(A\) tu menšiu z nich. Na rozdelenie postačí DFS prechod.

Celková časová zložitosť bude \(O(2^{n/2}(n+m))\). Pre veľké \(n\) je \(2^{n/2}\) je oveľa, oveľa menšie ako \(2^n\), takže robiť optimalizáciu, ktorá by nám toto zabezpečila má zmysel.

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define For(i, n) for(int i = 0; i<(n); ++i)
#define mp make_pair
#define MOD 1000000007LL

typedef long long ll;
typedef pair<pair<int,int>,vector<int> > vertex;

vector<vector<int> > G;
vector<vector<vertex> > E;
vector<bool> T;
vector<int> C,B;

void dfs(int v, int f) {
    T[v]=true;
    if(f==0) C.push_back(v);
    else B.push_back(v);
    For(i,G[v].size()) {
        int w=G[v][i];
        if(T[w]) continue;
        dfs(w,(f+1)%2);
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    G.resize(n);
    E.resize(n);
    For(i,m) {
        int x,y,a,b,c,d;
        scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
        vector<int> pom; pom.push_back(a); pom.push_back(b); pom.push_back(c); pom.push_back(d);
        E[x].push_back(mp(mp(x,y),pom));
        E[y].push_back(mp(mp(x,y),pom));
    }
    T.resize(n,false);
    For(i,n)
        if(!T[i]) dfs(i,0);
    if(C.size() > B.size()) swap(C,B);
    vector<int> F; F.resize(n,-1);
    int p=C.size();
    ll res=0;
    For(i,1<<p) {
        For(j,p) {
            if(i&(1<<j)) F[C[j]]=0;
            else F[C[j]]=1;
        }
        ll zat=1;
        For(j,n) {
            if(F[j]!=-1) continue;
            ll suc0=1,suc1=1;
            For(k,E[j].size()) {
                if(E[j][k].first.first==j && F[E[j][k].first.second]==0) 
                    {suc0*=E[j][k].second[0]; suc1*=E[j][k].second[2];}
                if(E[j][k].first.first==j && F[E[j][k].first.second]==1) 
                    {suc0*=E[j][k].second[1]; suc1*=E[j][k].second[3];}
                if(E[j][k].first.second==j && F[E[j][k].first.first]==0) 
                    {suc0*=E[j][k].second[0]; suc1*=E[j][k].second[1];}
                if(E[j][k].first.second==j && F[E[j][k].first.first]==1) 
                    {suc0*=E[j][k].second[2]; suc1*=E[j][k].second[3];}
                suc0%=MOD; suc1%=MOD;
            }
            zat=(suc0*zat+suc1*zat)%MOD;
        }
        res=(res+zat)%MOD;
    }
    printf("%d\n",(int)res);
}

  1. Namiesto menšej polovice sme mali napísať menšiu partíciu ale bolo by to zrozumiteľnejšie?

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.