xml地图|网站地图|网站标签 [设为首页] [加入收藏]

正规赌博平台

当前位置:网上十大正规赌博平台 > 正规赌博平台 > POJ 3308 Paratroopers,pojparatroopers

POJ 3308 Paratroopers,pojparatroopers

来源:http://www.nb-machinery.com 作者:网上十大正规赌博平台 时间:2019-08-22 03:48

POJ 3308 Paratroopers,pojparatroopers

Paratroopers

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 8940   Accepted: 2696

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 × ngrid 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       二分图最小点权覆盖集 对于一个敌人拆成两个点$x,y$ 从$S$向$x$连给定权值的边, 从$y$向$T$连给定权值的边, 从$x$向$y$连$INF$的边 二分图最小点权覆盖集=最小割=最大流 乘法取log变加法 mmp精度坑死人  

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define AddEdge(x,y,z) add_edge(x,y,z),add_edge(y,x,0);
using namespace std;
const int MAXN=100001;
double INF=2000000000;
const double eps=1e-9;
int N,M,P,S,T;
struct node
{
    int u,v,nxt;
    double flow;
}edge[MAXN*5];
int head[MAXN],cur[MAXN],num=0;
inline void add_edge(int x,int y,double z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].flow=z;
    edge[num].nxt=head[x];
    head[x]=num  ;
}
int deep[MAXN];
inline bool BFS()
{
    memset(deep,0,sizeof(deep));
    deep[S]=1;
    queue<int>q;
    q.push(S);
    while(q.size()!=0)
    {
        int p=q.front();
        q.pop();
        for(int i=head[p];i!=-1;i=edge[i].nxt)
            if(!deep[edge[i].v]&&edge[i].flow>eps)
            {
                deep[edge[i].v]=deep[p] 1;q.push(edge[i].v);
                if(edge[i].v==T) return 1;
            }
    }
    return deep[T];
}
double DFS(int now,double nowflow)
{
    if(now==T||nowflow<eps)    return nowflow;
    double totflow=0;
    for(int &i=cur[now];i!=-1;i=edge[i].nxt) 
    {
        if(deep[edge[i].v]==deep[now] 1&&edge[i].flow>eps)
        {
            double canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
            if(canflow>eps)
            {
                   edge[i].flow-=canflow;
                edge[i^1].flow =canflow;
                   totflow =canflow;
                   nowflow-=canflow;    
            }
            if(nowflow<eps) break;
        }
    }
    return totflow;
}
double Dinic()
{
    double ans=0;
    while(BFS())
    {
        memcpy(cur,head,sizeof(head)); 
        ans =DFS(S,INF);
    }
    return ans;    
}
double valr,valc;
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int test;
    scanf("%d",&test);
    while(test--)
    {
        memset(head,-1,sizeof(head));
        scanf("%d%d%d",&N,&M,&P);S=0;T=N M P;
        for(int i=1;i<=N;i  ) scanf("%lf",&valr),AddEdge(S,i,log(valr) );
        for(int i=1;i<=M;i  ) scanf("%lf",&valc),AddEdge(i N,T,log(valc) );
        for(int i=1;i<=P;i  ) 
        {
            int x,y;
            scanf("%d%d",&x,&y);
            AddEdge(x,y N,INF);
        }
        printf("%.4lfn",exp(Dinic()));
    }

    return  0;
}

 

3308 Paratroopers,pojparatroopers Paratroopers Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8940 Accepted: 2696 Description It is year 2500 A.D. and there is a...

POJ 1422 Air Raid,poj1422airraid

Air Raid

Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 8767   Accepted: 5240

Description

Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles. 

With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper. 

Input

Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format: 

no_of_intersections 
no_of_streets 
S1 E1 
S2 E2 
...... 
Sno_of_streets Eno_of_streets 

The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town's streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections. 

There are no blank lines between consecutive sets of data. Input data are correct. 

Output

The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town. 

Sample Input

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

Sample Output

2
1

Source

Dhaka 2002     最小路径覆盖问题 最小路径覆盖=点数-二分图最大匹配数  

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=1001;
int vis[MAXN];
int link[MAXN];
int map[MAXN][MAXN];
int N,M;
bool dfs(int x)
{
    for(int i=1;i<=N;i  )
    {
        if(map[x][i]&&!vis[i])
        {
            vis[i]=1;
            if(!link[i]||dfs(link[i]))
            {
                link[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
struct S
{
    int tall;
    string a,b,c;
}s[MAXN];

int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int Test;
    scanf("%d",&Test);
    while(Test--)
    {
        memset(vis,0,sizeof(vis));
        memset(link,0,sizeof(link));
        memset(map,0,sizeof(map));
        scanf("%d%d",&N,&M);
        for(int i=1;i<=M;i  )
        {
            int x,y;
            scanf("%d%d",&x,&y);
            map[x][y]=1;
        }
        int ans=0;
        for(int i=1;i<=N;i  )
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i))
                ans  ;
        }
        printf("%dn",N-ans );
    }
    return 0;
}

 

1422 Air Raid,poj1422airraid Air Raid Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8767 Accepted: 5240 Description Consider a town where all the streets are one...

C/C ,cc

出自:

1.头文件中只做声明。

  全局变量声明:

extern int var;

  全局函数声明:

void test(void);

2.extern作用

  当extern不与"C"在一起修饰变量或函数时,如在头文件中: extern int g_Int; 它的作用就是声明函数或全局变量的作用范围的关键字。

  当extern与"C"一起连用时,如: extern "C" void fun(int a, int b);则告诉编译器在编译fun这个函数名时按着C的规则去翻译相应的函数名而不是C 的,

//在.h文件的头上
#ifdef __cplusplus
#if __cplusplus
extern "C"{
#endif
#endif /* __cplusplus */ 
…
…
//.h文件结束的地方
#ifdef __cplusplus
#if __cplusplus
}
#endif
#endif /* __cplusplus */ 

 

出自: 1.头文件中只做声明。 全局变量声明: extern int var ; 全局函数声明: v...

本文由网上十大正规赌博平台发布于正规赌博平台,转载请注明出处:POJ 3308 Paratroopers,pojparatroopers

关键词: SG电子游戏

上一篇:删除字符串中的指定字符,关联容器

下一篇:没有了