Power Line
| Time limit: | 5sec. | Submitted: | 269 |
| Memory limit: | 64M | Accepted: | 84 |
Source: 2009 China North East Local Contest
|
Problem Description While DUT is hosting this NECPC Contest, in order to control the expenditure, Input Details The first line of the input contains an integer T, which indicates the number For each test case, there are three positive integers in the first row, n, m, In the following n rows, i-th line has m positive integers indicating the In the last row, there are m positive integers, ci (0 < ci < 5,0 <= Output Details For each case, if the layout of computers and power lines are not reasonable, Otherwise, output the lowest total price for power lines. Sample Input
1 2 2 1 1 3 2 2 1 1
Sample Output
4
Hint: You many link the first computer with the first power-points, and link the |
二分+多重匹配
水水更健康
#include<cstdio>
#include<cstring>
const int inf=0x7fffffff;
int mat[500][500],link[500][500];
bool map[500][500],usedif[500];
int n,m,p,rmin,rmax;
int lim[500];
bool flag;
bool can(int t)
{
for(int i=1; i<=m; i++)
{
if(usedif[i]==0&&map[t][i])
{
usedif[i]=1;
if(link[i][0]<lim[i])
{
link[i][++link[i][0]]=t;
return true;
}
else
{
for(int j=1; j<=link[i][0]; j++)
if(can(link[i][j]))
{
link[i][j]=t;
return true;
}
}
}
}
return false;
}
bool check(int limit)
{
memset(map,false,sizeof(map));
for(int i=1; i<=m; i++) link[i][0]=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(mat[i][j]<=limit) map[i][j]=true;
for(int i=1; i<=n; i++)
{
memset(usedif,0,sizeof(usedif));
if(!can(i)) return false;
}
return true;
}
int find()
{
int high=rmax,low=rmin;
int ans=high;
flag=false;
while(low<high)
{
int mid=(low+high)>>1;
if(check(mid))
{
flag=true;
if(mid<ans) ans=mid;
high=mid;
}
else low=mid+1;
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&p);
rmin=inf;
rmax=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&mat[i][j]);
if(mat[i][j]<rmin) rmin=mat[i][j];
if(mat[i][j]>rmax) rmax=mat[i][j];
}
for(int i=1;i<=m;i++) scanf("%d",&lim[i]);
int t=find();
if(flag) printf("%d/n",p*n*t);
else printf("-1/n");
}
return 0;
}
网络流解法，耗时差不多，0.2S左右
#include<cstdio>
#include<cstring>
const int N=1510;
const int M=60001;
const int inf=0x7fffffff;
int head[N];
int lim[N];
int map[N][N];
struct Edge
{
int v,next,w;
} edge[M];
int cnt,s,t;
int n,m,p;
bool flag;
int rmin,rmax,nn;
void addedge(int u,int v,int 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++;
}
int sap()
{
int pre[N],cur[N],dis[N],gap[N];
int flow=0,aug=inf,u;
bool flag;
for(int i=0; i<n; i++)
{
cur[i]=head[i];
gap[i]=dis[i]=0;
}
gap[s]=n;
u=pre[s]=s;
while(dis[s]<n)
{
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<aug) aug=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)
{
mindis=dis[v];
cur[u]=j;
}
}
if((--gap[dis[u]])==0)
break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return flow;
}
bool check(int limit)
{
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=nn;i++) addedge(s,i,1);
for(int i=1;i<=m;i++) addedge(i+nn,t,lim[i]);
for(int i=1;i<=nn;i++)
for(int j=1;j<=m;j++)
if(map[i][j]<=limit) addedge(i,j+nn,1);
if(sap()==nn) return true;
return false;
}
int solve()
{
flag=false;
int head=rmin,end=rmax;
int ans=end;
while(head<end)
{
int mid=(head+end)>>1;
if(check(mid))
{
if(ans>mid) ans=mid;
flag=true;
end=mid;
}
else head=mid+1;
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&p);
s=0;
t=n+m+1;
rmin=inf;
rmax=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]<rmin) rmin=map[i][j];
if(map[i][j]>rmax) rmax=map[i][j];
}
for(int i=1;i<=m;i++) scanf("%d",&lim[i]);
nn=n;
n=n+m+2;
int tt=solve();
if(flag) printf("%d/n",p*nn*tt);
else printf("-1/n");
}
return 0;
}