POJ 3308 Paratroopers//최소 베기

Paratroopers
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 2357
 
Accepted: 753
Description
It is year 2500 A.D. and there is a terrible war between the forces of the Earth and the Mars. Recently, the commanders of the Earth are informed by their spies that the invaders of Mars want to land some paratroopers in the m × n grid yard of one their main weapon factories in order to destroy it. In addition, the spies informed them the row and column of the places in the yard in which each paratrooper will land. Since the paratroopers are very strong and well-organized, even one of them, if survived, can complete the mission and destroy the whole factory. As a result, the defense force of the Earth must kill all of them simultaneously after their landing.
In order to accomplish this task, the defense force wants to utilize some of their most hi-tech laser guns. They can install a gun on a row (resp. column) and by firing this gun all paratroopers landed in this row (resp. column) will die. The cost of installing a gun in the ith row (resp. column) of the grid yard is ri (resp. ci ) and the total cost of constructing a system firing all guns simultaneously is equal to the product of their costs. Now, your team as a high rank defense group must select the guns that can kill all paratroopers and yield minimum total cost of constructing the firing system.
Input
Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing three integers 1 ≤ m ≤ 50 , 1 ≤ n ≤ 50 and 1 ≤ l ≤ 500 showing the number of rows and columns of the yard and the number of paratroopers respectively. After that, a line with m positive real numbers greater or equal to 1.0 comes where the ith number is ri and then, a line with n positive real numbers greater or equal to 1.0 comes where the ith number is ci. Finally, l lines come each containing the row and column of a paratrooper.
Output
For each test case, your program must output the minimum total cost of constructing the firing system rounded to four digits after the fraction point.
Sample Input

1
4 4 5
2.0 7.0 5.0 2.0
1.5 2.0 2.0 8.0
1 1
2 2
3 3
4 4
1 4

Sample Output

16.0000

Source
Amirkabir University of Technology Local Contest 2006
 
 
제1판에 들어가니 매우 기쁘다
이 문제의 구도를 나는 일찍이 앞에서 시합을 한 적이 있는데, 당시에는 풀지 못했는데, 지금은 도대체 어떤 문제인지 줄곧 생각나지 않는다. 생각나는 구두가 있으면 나에게 고소해라
고맙다
 
이 문제의 구도를 다시 한 번 말씀드릴게요.
최소 권한 집합 덮어쓰기
하하
바로 최소점 커버 BOSS 버전입니다.
 
최소 점 집합으로 덮어쓰는 모델은 말할 것도 없고, 최소 점 집합으로 E를 덮어쓰는 것이다.이어서 말하고 싶은 것은, 내가 일련의 최소 집합을 덮어쓴 후, 나는
최소 집합 덮어쓰기는 그 가장 원시적인 모델에 비칠 수 있다. 바로 그 소행 소열의 행렬이다.
 
최소 권한 집합 덮어쓰는 제목은 최소 베기로 완벽하게 실현할 수 있습니다.
구도를 보면 좀 쉬운 것 같아요.
아니면 두 개의 점, 하나의 슈퍼 원천점, 하나의 슈퍼 외환점 증가
마찬가지로, 줄 집합을 왼쪽에 놓고, 열을 오른쪽에 결합시키고, 줄 집합과 슈퍼 원점은 가장자리를 연결하고, 가장자리의 값은 줄의 값을 없애는 것이다
열과 환점이 연결되어 있고, 변의 권치는 소멸열의 권치이다
이어서 행렬이 교차하는 지점에 위병이 있으면 가장자리까지 이어져 가장자리가 무궁무진하다
 
이렇게 최소 절단을 구성하는 의미는 무엇에 있는가
간단하다. 우선 X->Y의 가장자리가 무궁무진하기 때문에 가장 적게 베이지 않는다
그러면 S-->X, Y->T 모서리를 잘라냅니다.
이어서 왜 가장 작은 베는 것이 이 모든 가장자리를 덮는 것에 대응하는지 앞의 일지에서 설명할 수 있다.
 
 
#include
#include
#include
const int N=102;
const int M=2001;
const double inf=1e10;
int head[N];
struct Edge
{
    int v,next;
    double w;
} edge[M];
int cnt,n,s,t;
void addedge(int u,int v,double w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].w=0;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
double sap()
{
    int pre[N],cur[N],dis[N],gap[N];
    double flow=0,aug=inf;
    int u;
    bool flag;
    for(int i=0; i    {
        cur[i]=head[i];
        gap[i]=dis[i]=0;
    }
    gap[s]=n;
    u=pre[s]=s;
    while(dis[s]    {
        flag=0;
        for(int &j=cur[u]; j!=-1; j=edge[j].next)
        {
            int v=edge[j].v;
            if(edge[j].w>0&&dis[u]==dis[v]+1)
            {
                flag=1;
                if(edge[j].w                pre[v]=u;
                u=v;
                if(u==t)
                {
                    flow+=aug;
                    while(u!=s)
                    {
                        u=pre[u];
                        edge[cur[u]].w-=aug;
                        edge[cur[u]^1].w+=aug;
                    }
                    aug=inf;
                }
                break;
            }
        }
        if(flag) continue;
        int mindis=n;
        for(int j=head[u]; j!=-1; j=edge[j].next)
        {
            int v=edge[j].v;
            if(edge[j].w>0&&dis[v]            {
                mindis=dis[v];
                cur[u]=j;
            }
        }
        if((--gap[dis[u]])==0)
            break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return flow;
}
int main()
{
    int m,l,T;
    double x;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&l);
        s=0;
        t=n+m+1;
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<=n;i++)
        {
            scanf("%lf",&x);
            addedge(0,i,log(x));
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%lf",&x);
            addedge(i+n,n+m+1,log(x));
        }
        for(int i=1;i<=l;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            addedge(a,b+n,inf);
        }
        n=n+m+2;
        printf("%.4lf/n",exp(sap()));
    }
    return 0;
}