Настройки поиска (Страница 8 из 9)

KADR пишет:

Можно довольно простой динамикой по дереву сделать за О(Н).
Выделим какую-то вершину как корень и топологически отсортируем дерево. Теперь пусть f(v) это максимальный путь в поддереве с корнем в вершине v, такой что оба его конца лежат в этом поддереве, а g(v) это максимальный путь в поддереве с корнем в v, такой что один его конец это лист этого поддерева, а второй - вершина v.
Тогда f(v)=max(f(v')) для всех потомков. Но считая его так мы не учтем, что может быть путь как бы "соединяется" в вершине v, поэтому в этот max следует еще включить 2 потомка v1 и v2, для которых g(v1)+edge(v,v1)+g(v2)+edge(v,v2) - максимально. Это легко сделать за О(количество потомков).
g(v)=max(g(v')+edge(v,v')) для всех потомков.
Тогда f(корень) и будет ответом.

Я не спорю с тобой
Но ведь они не понимает ДВС или БФС со всех вершин,то и динамику не поймут я думаю.

Задачи как таковой нету, просто возник вопрос.

Просто размер максимального паросочетания равен размеру максимального независимого множества.

Когда то писал эту задачу, код сохранился. По моему, он решает не на минимум, а на максимум, но за O(N^3)

#include <cstdio>
#include <cstring>

const int MAX=701;
int a[MAX][MAX];
int n;
int x[MAX], y[MAX], sx[MAX], sy[MAX], mx[MAX], my[MAX];

inline int get(int x,int y)
{
        return a[x][y]-mx[x]-my[y];
}

bool go(int cur)
{
        sx[cur]=1;
        for(int i=0;i<n;i++)
        {
                if(get(cur,i)==0)
                {
                        if(y[i]==-1)
                        {
                                sy[i]=cur;
                                while(1)
                                {
                                        int t=x[cur];
                                        x[cur]=i;
                                        y[i]=cur;
                                        if(~t)
                                        {
                                                cur=sy[t];
                                                i=t;
                                        }
                                        else break;
                                }
                                return true;
                        }
                }
        }
        for(int i=0;i<n;i++)
        {
                if(get(cur,i)==0)
                {
                        if(!sx[y[i]])
                        {
                                sy[i]=cur;
                                if(go(y[i]))
                                {
                                        return true;
                                }
                        }
                }
        }
        return false;
}

int main()
{
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
                mx[i]=-50000;
                for(int j=0;j<n;j++)
                {
                        scanf("%d",&a[i][j]);
                        if(a[i][j]>mx[i])mx[i]=a[i][j];
                }
        }
        for(int i=0;i<n;i++)
        {
                int m=-50000;
                for(int j=0;j<n;j++)
                {
                        int t=get(j,i);
                        if(t>m)m=t;
                }
                my[i]=m;
        }
        memset(x,-1,sizeof x);
        memset(y,-1,sizeof y);
        for(int sc=0;sc<n;sc++)
        {
                memset(sx,0,sizeof sx);
                memset(sy,-1,sizeof sy);
                bool b=go(sc);
                while(!b)
                {
                        int m=-50000, dx;
                        for(int i=0;i<n;i++)
                        {
                                if(sx[i])
                                {
                                        for(int j=0;j<n;j++)
                                        {
                                                if(!(~sy[j]))
                                                {
                                                        int t=get(i,j);
                                                        if(m<t)
                                                        {
                                                                m=t;
                                                                dx=i;
                                                        }
                                                }
                                        }
                                }
                        }
                        for(int i=0;i<n;i++)
                        {
                                if(sx[i])mx[i]+=m;
                                if(~sy[i])my[i]-=m;
                        }
                        b=go(dx);
                }
        }
        for(int i=0;i<n;i++)
        {
                printf("%d ",x[i]+1);
        }
}