【题目描述】

贝西经营着一家旅行社，一天贝西带着几队游客沿着亚马逊河旅行，河的两边分布着一些景点，每个景点都对应着一个观赏值。景点间由一些穿过河流的道路相连(位于河流同一侧的景点间没有直接道路相连)，贝西想要设计游客的旅行线路，使得该线路经过的景点的总的观赏值最大。

但是，贝西可能同时带着几个旅行团，贝西希望它给安排的旅行线路不能相交。

两条线路 (a <-> x) 和 (b <-> y) 出现如下情况之一就算相交:

if(a < b and y < x) or (a > b and x < y) or (a = b and x = y).

帮助贝西找出最佳旅行线路，贝西可以从任意景点开始，在任意景点结束。

【输入格式】

第一行，三个空格间隔的整数N (1 <= N <= 40,000), M (1 <=M <= 40,000), and R (0<= R <= 100,000) 。N表示河岸左边的景点数，M表示河岸右边的景点数，R表示道路的条数

接下来N行，每行一个整数，表示河岸左边对应景点的观赏值。

接下来M行，每行一个整数，表示河岸右边对应景点的观赏值。

接下来R行，每行两个空格间隔的整数X,Y，表示左岸的X号景点与右岸的Y号景点间有道路直接相连。

(0 <= 观赏值<= 40,000)

【输出格式】

一个整数，表示所求最大观赏值。

【样例输入】

3 2 4

1

1

5

2

2

1 1

2 1

3 1

2 2

【样例输出】

8

【分析】

首先可以看出这题不能用贪心解决。

一种比较明显的思路就是双重循环枚举两个点后DP，但是更明显的是这样做的时间复杂度根本不能承受。

联想到克鲁斯卡尔算法与普利姆算法的区别，我们想到以边作为状态。首先要排序（去除后效性），然后设f1[i]表示左边以i结尾的最大收益，f2[i]表示右边以i结尾的最大收益，状态转移方程就很明显了。

转移的时候注意用临时变量存储。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define maxn 40005#define maxe 100005typedef long long LL;typedef pair
         
           pii;int n,m,k;LL a[maxn],b[maxn],f1[maxn],f2[maxn];pii e[maxe];int main(){    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=n;i++) scanf("%d",&a[i]);    for(int i=1;i<=m;i++) scanf("%d",&b[i]);    for(int i=1;i<=k;i++) scanf("%d%d",&e[i].first,&e[i].second);    sort(e+1,e+k+1);    memcpy(f1,a,sizeof(a));    memcpy(f2,b,sizeof(b));    for(int i=k;i>=1;i--) {        int u=e[i].first,v=e[i].second;        LL va=a[u]+f2[v];        LL vb=b[v]+f1[u];        f1[u]=max(f1[u],va);        f2[v]=max(f2[v],vb);    }    int ans=0;    for (int i=1;i<=n;i++) if (ans