|
|
Posted on 2010-10-06 19:25 成幸毅 阅读(303) 评论(0) 编辑 收藏 引用
floyd + 二分 + sap 对于点权值的的最大流需要拆点构图，把权值边放到一个数组里面，进行排序，然后枚举答案，这题再怎么简化还是很长。
 #include<iostream>
#include<algorithm>
using namespace std ;
const int N = 510 ;
const int Inf = 1<<30 ;
int fn,pn,total,s,t,cow[N],col[N],map[N][N],Length;
__int64 d[N][N],stack[N*N];
void floyd()
   {
 for(int k=1;k<=fn;k++)
  {
for(int i=1;i<=fn;i++)
{
for(int j=1;j<=fn;j++)
{
if(d[i][k]!=-1&&d[k][j]!=-1&&(d[i][j]==-1||d[i][j]>d[i][k]+d[k][j]))
d[i][j] = d[i][k]+d[k][j] ;
 }
}
}
__int64 tmp[N*N] ;
int cnt = 0 ;
Length = 0 ;
for(int i=1;i<=fn;i++)
for(int j=1;j<=fn;j++)
if(d[i][j]!=-1) tmp[cnt++] = d[i][j] ;
sort(tmp,tmp+cnt);
for(int i=0;i<cnt;i++)
{
if(tmp[i]==tmp[i+1]) continue ;
stack[Length++] = tmp[i] ;
}
 }
void Bulid_Graph(__int64 num)
{
memset(map,0,sizeof(map));
for(int i=1;i<=fn;i++)
{
if(cow[i]) map[s][i] = cow[i] ;
if(col[i]) map[i+fn][t] = col[i] ;
map[i][i+fn] = Inf ;
}
for(int i=1;i<=fn;i++)
{
for(int j=1;j<=fn;j++)
{
if(d[i][j]!=-1&&d[i][j]<=num)
map[i][j+fn] = map[j][i+fn] = Inf ;
}
}
}
int Min(int minflow,int aug)
{
if(aug==-1||minflow<aug) return minflow ;
return aug ;
}
int sap()
{
int u,gap[N],dis[N],pre[N],aug=-1,maxflow=0;
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
u=pre[s]=s;
gap[0]=t+1;
while(dis[s]<t+1)
{
loop: for(int i=0;i<=t;i++)
{
if(map[u][i]&&dis[u]==dis[i]+1)
{
aug = Min(map[u][i],aug);
pre[i] = u ;
u = i ;
if(u==t)
{
maxflow += aug ;
for(int v=t;v!=s;v=pre[v])
{
map[pre[v]][v] -= aug ;
map[v][pre[v]] += aug ;
}
aug = -1 ;
u = s ;
}
goto loop ;
}
}
int mindis = t ;
for(int i=0;i<=t;i++)
if(map[u][i]&&dis[i]<mindis)
mindis = dis[i] ;
if((--gap[dis[u]])==0) break;
gap[dis[u] = mindis + 1] ++ ;
u = pre[u] ;
}
return maxflow ;
}
bool check(int id)
{
Bulid_Graph(stack[id]);
int maxflow =sap() ;
if(maxflow==total) return true ;
return false ;
}
int main()
{
while(scanf("%d%d",&fn,&pn)!=EOF)
{
total = 0 ;
for(int i=1;i<=fn;i++)
{
scanf("%d%d",&cow[i],&col[i]);
total += cow[i] ;
}
int a,b ;
__int64 v;
memset(d,-1,sizeof(d));
for(int i=1;i<=pn;i++)
{
scanf("%d%d %I64d",&a,&b,&v);
if(d[a][b]==-1||d[a][b]>v)
d[a][b] = d[b][a] = v ;
}
s=0;
t=2*fn+1;
floyd() ;
int left = 0 , right = Length - 1 , flag = 0 ;
while(left<=right)
{
int mid = (left+right)>>1 ;
if(check(mid))
{
right = mid - 1 ;
flag = 1 ;
}
else left = mid + 1 ;
}
if(0==flag) printf("-1\n");
else printf("%I64d\n",stack[right+1]);
}
return 0 ;
}
|