hdoj1068 最大独立集
小试一下写的模板
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 10010 #define maxe 2000010 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 int color[maxn]; inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { if(color[i]==2) continue; memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } void dfs2(int cur,int c) { color[cur]=c; for(int i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(color[v]==3-c) continue; dfs2(v,3-c); } return; } int main() { int i,j; int u,v; while(~scanf("%d",&n)) { int num; cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) { scanf("%d: (%d)",&u,&num);u++; for(j=1;j<=num;j++) { scanf("%d",&v);v++; add(u,v);add(v,u); } } memset(color,0,sizeof(color)); for(i=1;i<=n;i++) if(!color[i]) dfs2(i,1); int ans=xyl(); printf("%d\n",n-ans); } return 0; }
hdoj1150
题意:两个机器,第一个机器有n1种模式,第二个机器有n2种模式,给出m个任务,每个任务可以用机器一的某一模式或机器二的某一模式完成,切换模式需要重启机器,两个机器初始都是模式0,问完成这些任务最少需要重启几次。
思路:建立二分图:X部n1个点,Y部n2个点,一个任务可以在机器一的模式u或机器二的模式v下完成,则连边(u,n1+v)。这样,图中的每条边相当于一个任务,现在要求完成所有任务所需的最少重启次数,本质就是选出最少的点来覆盖所有的边,即二分图的最小点覆盖。
注意:由于初始是0模式,所以端点为0的边是不用连的,因为不用重启就可以完成这些任务。
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 300+10 #define maxe 10000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n1,n2,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n1;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int main() { int i,j; int u,v; while(~scanf("%d",&n1) && n1!=0) { scanf("%d%d",&n2,&m); cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=m;i++) { scanf("%d%d%d",&j,&u,&v); if(!u || !v) continue; u++;v++; add(u,n1+v);add(n1+v,u); } int ans=xyl(); printf("%d\n",ans); } return 0; }
hdoj1151
DAG的最小路径覆盖
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 300+10 #define maxe 40000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m,cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int main() { int i,j,t; int u,v; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); cnt=0;memset(head,-1,sizeof(head)); while(m--) { scanf("%d%d",&u,&v); add(u,n+v); } printf("%d\n",n-xyl()); } return 0; }
hdoj1179 Ollivanders: Makers of Fine Wands since 382 BC.
裸题
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 200+10 #define maxe 10000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int main() { int i,j; while(~scanf("%d%d",&m,&n)) { cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) { int k; scanf("%d",&k); while(k--) { scanf("%d",&j); add(i,n+j); } } printf("%d\n",xyl()); } return 0; }
hdoj1281
在某篇网络流的论文中出现过类似的题,行列见图,以行为x部,列为y部。如果可以在(i,j)放车,那么连弧,求最大匹配。
关键边一定是最大匹配中的某些边,因此枚举删去最大匹配的边,求最大匹配即可。
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 300+10 #define maxe typedef struct Edge{ bool flag; int from; int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n1,n2,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 int match2[maxn]; inline void add(int u,int v) { edge[cnt].flag=1;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v] || !edge[i].flag) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n1;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int main() { int i,j; int u,v; int key,cases=0; while(scanf("%d%d%d",&n1,&n2,&m)!=EOF) { key=0;cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,n1+v); } int ans=xyl(); for(i=n1+1;i<=n1+n2;i++) match2[i]=match[i]; for(i=n1+1;i<=n1+n2;i++) { u=match2[i]; if(!u) continue; for(j=head[u];j!=-1;j=edge[j].next) { if(edge[j].to!=i) continue; edge[j].flag=0; v=j; break; } int tmp=xyl(); if(ans!=tmp) key++; edge[v].flag=1; } printf("Board %d have %d important blanks for %d chessmen.\n",++cases,key,ans); } return 0; }
hdoj1498 50 years, 50 colors
题意:给出n*n矩阵,map[i][j](1<=map[i][j]<=50)表示气球的颜色值。k表示可以操作k次,每次操作可以删除一行或一列的某同一颜色的气球。问哪种颜色的气球是无法通过k次操作删除完的。将结果升序排列,否则输出-1。
注意点:如果认为,对于某一颜色,如果该颜色分布在i行,j列,只要i>k && j>k就无法删除完就大错特错了,即使i>k && j>k仍然有可能通过选定某些行和某些列来消除完这种颜色的气球(画画图就能明白了)
思路:行列建图,对于颜色w,如果map[i][j]=w那么建弧,这样每条边就表示需要删除的点,那么对于点i(i<=n),选中i就表示删除了第i行上的颜色为w的气球,即覆盖了和i关联的边。那么问题的实质就是求最小点覆盖=ans,如果ans>k那么说明这种颜色的点不能通过k次操作消除完。
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 300+10 #define maxe 20000+10 typedef struct Edge{ bool flag; int w; int from; int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,k; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v,int w) { edge[cnt].flag=1;edge[cnt].w=w;edge[cnt].from=u;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v] || !edge[i].flag) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int ans[55],anscnt; int main() { int i,j; int u,v,tmp; while(~scanf("%d%d",&n,&k) && !(n==0 && k==0)) { anscnt=cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&tmp); add(i,n+j,tmp); } for(i=1;i<=50;i++) { bool in=0; for(j=0;j<=cnt-1;j++) if(edge[j].w!=i) edge[j].flag=0; else in=1; if(!in) {for(j=0;j<=cnt-1;j++) edge[j].flag=1;continue;} if(xyl()>k) ans[++anscnt]=i; for(j=0;j<=cnt-1;j++) edge[j].flag=1; } if(anscnt==0) {printf("-1\n");continue;} printf("%d",ans[1]); for(i=2;i<=anscnt;i++) printf(" %d",ans[i]); printf("\n"); } return 0; }
hdoj1507 Uncle Tom’s Inherited Land*
最大匹配,输出方案
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 20000+10 #define maxe 300+10 typedef struct Edge{ int from; int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].from=u;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool map[110][110]; inline bool judge(int x,int y) { if(1<=x && x<=n && 1<=y && y<=m && map[x][y]) return 1; return 0; } inline int index(int x,int y) { return (x-1)*m+y; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i,j; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if((i+j)&1) continue; int tmp=index(i,j); memset(use,0,sizeof(use)); if(dfs(tmp)) ans++; } return ans; } int main() { int i,j; int u,v,k; while(~scanf("%d%d",&n,&m) && !(n==0 && m==0)) { cnt=0;memset(head,-1,sizeof(head)); memset(map,1,sizeof(map)); scanf("%d",&k); while(k--) { scanf("%d%d",&u,&v); map[u][v]=0; } for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(!map[i][j] || (i+j)&1) continue; if(judge(i-1,j)) add(index(i,j),index(i-1,j)); if(judge(i+1,j)) add(index(i,j),index(i+1,j)); if(judge(i,j-1)) add(index(i,j),index(i,j-1)); if(judge(i,j+1)) add(index(i,j),index(i,j+1)); } printf("%d\n",xyl()); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(!((i+j)&1) || !match[index(i,j)]) continue; int tmp=match[index(i,j)]; int tmpx=tmp%m==0?tmp/m:tmp/m+1; int tmpy=tmp-tmp/m*m; if(!tmpy) tmpy=m; printf("(%d,%d)--(%d,%d)\n",tmpx,tmpy,i,j); } printf("\n"); } return 0; }
hdoj1528 Card Game Cheater
思路:对于第二个人的牌i和第一个人的牌j,如果牌i大于牌j,则连弧,做最大匹配即可
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 100+10 #define maxe 1000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int num[300]; char map1[30][2],map2[30][2]; bool greater(char a[],char b[]) { if(a[0]!=b[0]) return num[a[0]]>num[b[0]]; return num[a[1]]>num[b[1]]; } int main() { int i,j; int u,v; int t; for(i='2';i<='9';i++) num[i]=i-'0'-1; num['T']=9;num['J']=10;num['Q']=11;num['K']=12;num['A']=13; num['C']=1;num['D']=2;num['S']=3;num['H']=4; scanf("%d",&t); while(t--) { cnt=0;memset(head,-1,sizeof(head)); scanf("%d",&n);getchar(); for(i=1;i<=n;i++) { scanf("%c%c",&map1[i][0],&map1[i][1]); getchar(); } for(i=1;i<=n;i++) { scanf("%c%c",&map2[i][0],&map2[i][1]); getchar(); } for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(!greater(map2[i],map1[j])) continue; add(i,n+j); } printf("%d\n",xyl()); } return 0; }
hdoj2063 过山车
裸题
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 1000+10 #define maxe 1000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int main() { int i,j; int u,v,k; while(~scanf("%d",&k) && k) { scanf("%d%d",&n,&m); cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=k;i++) { scanf("%d%d",&u,&v); add(u,n+v); } printf("%d\n",xyl()); } return 0; }
hdoj2119 Matrix
最小点覆盖,与上面某题类似
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 200+10 #define maxe 10000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int main() { int i,j; int tmp; while(~scanf("%d",&n) && n) { scanf("%d",&m); cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&tmp); if(!tmp) continue; add(i,n+j); } printf("%d\n",xyl()); } return 0; }
hdoj2444 The Accomodation of Students
先交叉染色判断是否是二分图,在做最大匹配
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 200+10 #define maxe 40000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int color[maxn]; bool dfs2(int cur,int c) { if(color[cur]==c) return 1; if(color[cur]==3-c) return 0; color[cur]=c; for(int i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!dfs2(v,3-c)) return 0; } return 1; } int main() { int i,j; int u,v; while(~scanf("%d%d",&n,&m)) { cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v);add(v,u); } memset(color,0,sizeof(color)); if(!dfs2(1,1)) {printf("No\n");continue;} printf("%d\n",xyl()/2); } return 0; }
hdoj1045 Fire Net
思路:经典的行列建图变形,由于有了墙壁,所以不是每行每列只能有一个,其实质是需要自己计算一个格子所处的“行”和“列”。
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 100+10 #define maxe 10000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } char map[5][5]; int row[5][5],col[5][5]; int main() { int i,j; int u,v; while(~scanf("%d",&n) && n) { getchar(); cnt=0;memset(head,-1,sizeof(head)); char tmpr[30],tmpc[30]; int rx[30],ry[30]; int cx[30],cy[30]; int count1=0,count2=0; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%c",&map[i][j]); tmpr[++count1]=map[i][j]; rx[count1]=i;ry[count1]=j; } tmpr[++count1]='X'; getchar(); } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { tmpc[++count2]=map[j][i]; cx[count2]=j;cy[count2]=i; } tmpc[++count2]='X'; } int cur; cur=0;i=1; while(tmpr[i]=='X' && i<=count1) i++; while(i<=count1) { cur++; while(i<=count1 && tmpr[i]=='.') { row[rx[i]][ry[i]]=cur;i++; } while(i<=count1 && tmpr[i]=='X') i++; } int nn=cur; i=1; while(tmpc[i]=='X' && i<=count2) i++; while(i<=count2) { cur++; while(i<=count2 && tmpc[i]=='.') { col[cx[i]][cy[i]]=cur;i++; } while(i<=count2 && tmpc[i]=='X') i++; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(map[i][j]=='X') continue; add(row[i][j],col[i][j]); } n=nn; printf("%d\n",xyl()); } return 0; }
hdoj1350 Taxi Cab Scheme
如果某个cab在完成任务i后还可以完成j,那么在i任务的结束点向j任务的开始点连边
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<stdlib.h> #include<string.h> #define maxn 4000+10 #define maxe 1000000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } typedef struct Point{ int x,y; }Point; Point bp[510],ep[510]; int bt[510],et[510]; int dist(Point a,Point b) { return abs(a.x-b.x)+abs(a.y-b.y); } int main() { int i,j,t; int u,v; scanf("%d",&t); while(t--) { scanf("%d",&n); int h,m; cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) { scanf("%d:%d %d%d%d%d",&h,&m,&bp[i].x,&bp[i].y,&ep[i].x,&ep[i].y); bt[i]=h*60+m;et[i]=bt[i]+dist(bp[i],ep[i]); add(i,3*n+i); } for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i==j) continue; if(et[i]+dist(ep[i],bp[j])+1<=bt[j]) add(n+i,2*n+j); if(et[j]+dist(ep[j],bp[i])+1<=bt[i]) add(n+j,2*n+i); } n*=2; printf("%d\n",n-xyl()); } return 0; }
hdoj3118 Arbiter
题意:最少去掉几条边可以使图不含奇圈。
思路:一个图是二分图的充要条件是它不含奇圈,且含有至少两个点。由于n很小,所以可以二进制枚举二分图的X部和Y部,然后判断要去掉几条边。
#include<stdio.h> #include<string.h> #define maxn 20 #define maxe 90000+10 typedef struct Edge{ int from; int to; int next; }Edge; Edge edge[maxe]; int head[maxn],cnt; int n,m; int ans; void add(int u,int v) { edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } int main() { int t; int i,j; int u,v; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); ans=100000000;cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); } for(i=0;i<=(1<<n)-1;i++) { int tmp=0; for(j=0;j<=cnt-1;j++) { u=edge[j].from;v=edge[j].to; if(((i&(1<<u)) && (i&(1<<v))) || (!(i&(1<<u)) && !(i&(1<<v)))) tmp++; } if(tmp<ans) ans=tmp; } printf("%d\n",ans); } return 0; }
hdoj3729 I’m Telling the Truth
思路:求字典序最大的二分匹配方案,做匈牙利算法的时候倒着枚举二分图一边的点即可
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #include<algorithm> #define maxn 100100+10 #define maxe 10000000+10 using namespace std; typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=n;i>=1;i--) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int main() { int i,j,t; int u,v; scanf("%d",&t); while(t--) { scanf("%d",&n); cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) { scanf("%d%d",&u,&v); for(j=u;j<=v;j++) add(i,n+j); } int num=xyl(); printf("%d\n",num); int ans[100],count=0; for(i=n+1;i<=n+100000;i++) if(match[i]) { ans[++count]=match[i]; } sort(ans+1,ans+1+count); bool flag=1; for(i=1;i<=num;i++) { if(flag){printf("%d",ans[i]);flag=0;} else printf(" %d",ans[i]); } printf("\n"); } return 0; }
hdoj2389 Rain on your Parade
匈牙利果断TLE
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #include<math.h> #define maxn 6000+10 #define maxe 9000000+10 #define eps 1e-8 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } typedef struct Point{ int x,y; }Point; Point p[maxn],b[maxn]; int sp[maxn]; double dist(Point a,Point b) { return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))); } int main() { int i,j,t; int u,v,cases=0; scanf("%d",&t); while(t--) { int time; double dis; cnt=0;memset(head,-1,sizeof(head)); scanf("%d%d",&time,&n); for(i=1;i<=n;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&sp[i]); scanf("%d",&m); for(i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { dis=dist(p[i],b[j]); if(dis<(double)(time*sp[i])+eps) add(i,n+j); } } printf("Scenario #%d:\n%d\n\n",++cases,xyl()); } return 0; }
hk无压力
/** hk算法O(sqrt(V)*E) 每次bfs找到的增广路集合中的增广路都是一样长的,且随着bfs,长度是递增的 **/ #include<stdio.h> #include<string.h> #include<queue> #include<math.h> #define maxn 3000+10 #define maxe 10000000+10 #define eps 1e-8 using namespace std; typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn],cnt; int n,m; int mx[maxn],my[maxn],dx[maxn],dy[maxn]; bool use[maxn]; void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool bfs() { int i; bool res=0; queue<int> q; for(i=1;i<=n;i++) if(!mx[i]) q.push(i); memset(dx,0,sizeof(dx)); memset(dy,0,sizeof(dy)); while(!q.empty()) { int u=q.front();q.pop(); for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!dy[v]) { dy[v]=dx[u]+1; if(!my[v]) res=1; else { dx[my[v]]=dy[v]+1; q.push(my[v]); } } } } return res; } bool dfs(int u) { int i,j; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(dy[v]==dx[u]+1) { dy[v]=0; if(!my[v] || dfs(my[v])) { mx[u]=v;my[v]=u; return 1; } } } return 0; } int hk() { int ans=0; memset(mx,0,sizeof(mx)); memset(my,0,sizeof(my)); while(bfs()) { for(int i=1;i<=n;i++) if(!mx[i] && dfs(i)) ans++; } return ans; } typedef struct Point{ int x,y; }Point; Point p[maxn],b[maxn]; int sp[maxn]; double dist(Point a,Point b) { return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))); } int main() { int i,j,t; int u,v,cases=0; scanf("%d",&t); while(t--) { int time; double dis; cnt=0;memset(head,-1,sizeof(head)); scanf("%d%d",&time,&n); for(i=1;i<=n;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&sp[i]); scanf("%d",&m); for(i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { dis=dist(p[i],b[j]); if(dis<(double)(time*sp[i])+eps) add(i,j); } } printf("Scenario #%d:\n%d\n\n",++cases,hk()); } return 0; }
hdoj1054 Strategic Game
思路:树的最小边覆盖,可以贪心或者dp或者当成二分图来做,因为无向树一定是二分图。
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 1500+10 #define maxe 3000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } int main() { int i,j; int u,v; while(~scanf("%d",&n)) { cnt=0;memset(head,-1,sizeof(head)); int num; for(i=1;i<=n;i++) { scanf("%d:(%d)",&u,&num);u++; for(j=1;j<=num;j++) { scanf("%d",&v);v++; add(u,v);add(v,u); } } printf("%d\n",xyl()/2); } return 0; }
hdoj3605 Escape
哈哈,第一道二分图多重匹配,以前用最大流a过,用最大流必须缩点,将具有相同选择状态的人合并
用匈牙利复杂度比最大流低,开始use数组开成了十万,结果memset一下下就超时了,慎用memset,,其实开成10+5就行了。
#include<stdio.h> #include<string.h> #define maxn 100010+10 #define maxe 2000000+10 #define maxl 100000+10 #define maxr 10+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxr]; int maxy[maxr],num[maxr],match[maxr][maxl]; inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i,j; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(num[v]<maxy[v]) { num[v]++; match[v][num[v]]=cur; return 1; } else { for(j=1;j<=num[v];j++) { if(dfs(match[v][j])) { match[v][j]=cur; return 1; } } } } return 0; } bool xyl() { int i; memset(num,0,sizeof(num)); for(i=m+1;i<=m+n;i++) { memset(use,0,sizeof(use)); if(!dfs(i)) return 0;//左侧i点出发找不到增广轨,那么以后也不会找到,即这个人无法匹配 } return 1; } void scan(int &num) //对G++使用 { char in; bool neg=false; while(((in=getchar()) > '9' || in<'0') && in!='-') ; if(in=='-') { neg=true; while((in=getchar()) >'9' || in<'0'); } num=in-'0'; while(in=getchar(),in>='0'&&in<='9') num*=10,num+=in-'0'; if(neg) num=0-num; } int main() { int i,j; int u,v,tmp; while(~scanf("%d%d",&n,&m)) { cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scan(tmp); if(tmp) add(m+i,j); } } for(i=1;i<=m;i++) scan(maxy[i]); printf("%s\n",xyl()?"YES":"NO"); } return 0; }
hdoj1669 Jamie’s Contact Groups
二分答案,做多重匹配
#include<stdio.h> #include<string.h> #define maxn 1500+10 #define maxe 750000+10 #define maxl 1000+10 #define maxr 500+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxr]; int maxy[maxr],num[maxr],match[maxr][maxl]; inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i,j; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(num[v]<maxy[v]) { num[v]++; match[v][num[v]]=cur; return 1; } else { for(j=1;j<=num[v];j++) { if(dfs(match[v][j])) { match[v][j]=cur; return 1; } } } } return 0; } bool xyl() { int ans=0,i; memset(num,0,sizeof(num)); for(i=m+1;i<=m+n;i++) { memset(use,0,sizeof(use)); if(!dfs(i)) return 0; } return 1; } int bsearch(int l,int r) { int mid; while(l<=r) { mid=(l+r)/2; for(int i=1;i<=m;i++) maxy[i]=mid; if(xyl()) r=mid-1; else l=mid+1; } return l; } int main() { int i,j; int u,v; char s[20]; while(scanf("%d%d",&n,&m)!=EOF && !(n==0 && m==0)) { cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) { scanf("%s",s); char c; int tmp=0; c=getchar(); c=getchar(); while(c!='\n') { if(c==' ') { add(m+i,tmp+1); tmp=0; } else { tmp=tmp*10+c-'0'; } c=getchar(); } add(m+i,tmp+1); } printf("%d\n",bsearch(1,1000)); } return 0; }
hdoj2236
思路:二分差值,在每次二分的时候枚举下界。如果是枚举下界,对于每个下界二分差值,结果无情的TLE了。。。
技巧:如果题目要求是左侧都要匹配,那么匈牙利算法改成if(!dfs(i)) return 0可以节省时间,因为一个点现在找不到增广轨,以后也肯定找不到。
/** 匈牙利算法O(nm) **/ #include<stdio.h> #include<string.h> #define maxn 200+10 #define maxe 10000+10 typedef struct Edge{ bool flag; int w; int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v,int w) { edge[cnt].w=w;edge[cnt].flag=1;edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { if(!edge[i].flag) continue; int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } bool xyl() { int i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(!dfs(i)) return 0; } return 1; } int ans,maxd,mind; int bsearch(int l,int r) { int i,j; int m; while(l<=r) { m=(l+r)/2; bool flag=0; for(i=1;i<=maxd-m;i++) { for(j=0;j<=cnt-1;j++) if(edge[j].w>=i && edge[j].w<=i+m) edge[j].flag=1; else edge[j].flag=0; if(xyl()) {flag=1;break;} } if(!flag) l=m+1; else r=m-1; } return l; } int main() { int i,j; int t,tmp; scanf("%d",&t); while(t--) { scanf("%d",&n); cnt=0;memset(head,-1,sizeof(head)); ans=0x3f3f3f3f,maxd=-1,mind=0x3f3f3f3f; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&tmp); add(i,n+j,tmp); if(tmp>maxd) maxd=tmp; if(tmp<mind) mind=tmp; } int maxcha=maxd-mind; printf("%d\n",bsearch(0,maxcha)); } return 0; }
hdoj1083 Courses
裸的最大匹配
#include<stdio.h> #include<string.h> #define maxn 400+10 #define maxe 120000+10 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m; int cnt; bool use[maxn]; int match[maxn];//match[i]表示i点匹配的点,i为右侧的点 inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { int i; for(i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } bool xyl() { int ans=0,i; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(!dfs(i)) return 0; } return 1; } int main() { int i,j; int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) { int cc,tmp; scanf("%d",&cc); for(j=1;j<=cc;j++) { scanf("%d",&tmp); add(i,n+tmp); } } if(xyl()) printf("YES\n"); else printf("NO\n"); } return 0; }
hdoj2458 Kindergarten
裸的二分图最大团
#include<stdio.h> #include<string.h> #define maxn 410 #define maxe 40010 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n1,n2,m,cnt; int match[maxn]; bool use[maxn]; void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { for(int i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; return 1; } } return 0; } int xyl() { int ans=0; memset(match,0,sizeof(match)); for(int i=1;i<=n1;i++) { memset(use,0,sizeof(use)); if(match[i]) continue; if(dfs(i)) ans++; } return ans; } bool map[210][210]; int main() { int i,j,cases=0; int u,v; while(~scanf("%d%d%d",&n1,&n2,&m) && !(n1==0 && n2==0 && m==0)) { cnt=0;memset(head,-1,sizeof(head)); memset(map,0,sizeof(map)); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); map[u][v]=1; } for(i=1;i<=n1;i++) for(j=1;j<=n2;j++) { if(!map[i][j]) add(i,n1+j); } printf("Case %d: %d\n",++cases,n1+n2-xyl()); } return 0; }
hdoj4160 Dolls
一个盒子只能装一个,so。。可以想到最小路径覆盖,一条路径的起始点不就是一个裸露在外的盒子吗
#include<stdio.h> #include<string.h> #define maxn 510 #define maxe 150010 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[2*maxn]; int n,m,cnt; int match[2*maxn]; bool use[maxn]; int a[510],b[510],c[510]; inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { for(int i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; match[cur]=v; return 1; } } return 0; } int xyl() { int ans=0; memset(match,0,sizeof(match)); for(int i=n+1;i<=n+n;i++) { memset(use,0,sizeof(use)); if(match[i]) continue; if(dfs(i)) ans++; } return ans; } int main() { int i,j; while(~scanf("%d",&n) && n) { cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i==j) continue; if(a[i]>a[j] && b[i]>b[j] && c[i]>c[j]) add(n+i,j); } printf("%d\n",n-xyl()); } return 0; }
hdoj4185
经典最大匹配。。
#include<stdio.h> #include<string.h> #define maxn 360000 #define maxe 10000000 typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n,m,cnt; int match[maxn]; bool use[maxn]; char map[610][610]; bool judge(int x,int y) { if(1<=x && x<=n && 1<=y && y<=n && map[x][y]=='#') return 1; return 0; } int index(int x,int y) { return (x-1)*n+y; } inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { for(int i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur;match[cur]=v; return 1; } } return 0; } int xyl() { int ans=0; memset(match,0,sizeof(match)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if((i+j)&1 || match[index(i,j)]) continue; for(int k=1;k<=n*n;k++) use[k]=0; if(dfs(index(i,j))) ans++; } return ans; } int main() { int i,j; int t,cases=0; scanf("%d",&t); while(t--) { scanf("%d",&n);getchar(); cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) scanf("%c",&map[i][j]); getchar(); } for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if((i+j)&1 || map[i][j]=='.') continue; int u=index(i,j); if(judge(i-1,j)) add(u,index(i-1,j)); if(judge(i+1,j)) add(u,index(i+1,j)); if(judge(i,j-1)) add(u,index(i,j-1)); if(judge(i,j+1)) add(u,index(i,j+1)); } printf("Case %d: %d\n",++cases,xyl()); } return 0; }
hdoj2413 Against Mammoths
题意:给出n1个h类星球,n2个a类星球,给出每个星球初始的飞船数量。给出每个星球造船速度p个/年,任意一个h类星球到任意一个a类星球的时间(年),现在要从h类星球派船征服a类星球,一个h类星球最多只能征服一个a类星球,且一个a类星球只能被一个h类星球征服。问征服所有a类星球最少需要多少时间,如果不能全部征服,输出IMPOSSIBLE
(如果从h类的i星派出x个飞船,到达a类的j星时,j星球有y个飞船,如果x>=y,h赢,否则a赢)
思路:二分时间,建立二分图,注意分两种情况讨论:
(1)当i的速率小于j时,那么“条件是不利的”,这时候造船越久越吃亏,所以对于h类星球的人,最优策略是一开始就出发派出该星所有飞船,如果这样还不能打败j星,则肯定不能打败,不建边
(2)除了(1)的情况,则二分给出的时间全用上看下能否打败,能则建边
ps:注意要用long long,太大也不行,会溢出,wa好多次。。
#include<stdio.h> #include<string.h> #define maxn 500+10 #define maxe 62500+10 typedef long long ll; typedef struct Edge{ int to; int next; }Edge; Edge edge[maxe]; int head[maxn]; int n1,n2,m,cnt; int match[maxn]; bool use[maxn]; inline void add(int u,int v) { edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++; return; } bool dfs(int cur) { for(int i=head[cur];i!=-1;i=edge[i].next) { int v=edge[i].to; if(use[v]) continue; use[v]=1; if(!match[v] || dfs(match[v])) { match[v]=cur; match[cur]=v; return 1; } } return 0; } int xyl() { int ans=0; memset(match,0,sizeof(match)); for(int i=1;i<=n1;i++) { if(match[i]) continue; memset(use,0,sizeof(use)); if(dfs(i)) ans++; } return ans; } ll init[3][300],rate[3][300],map[300][300]; ll bsearch(ll l,ll r) { ll m; int i,j; bool flag=0; while(l<=r) { m=l+(r-l)/2; cnt=0;memset(head,-1,sizeof(head)); for(i=1;i<=n1;i++) for(j=1;j<=n2;j++) { if(map[i][j]>m) continue; if(rate[1][i]<rate[2][j]) { ll numh=init[1][i]; ll numa=init[2][j]+map[i][j]*rate[2][j]; if(numh>=numa) add(i,n1+j); continue; } ll numa=init[2][j]+m*rate[2][j]; ll numh=init[1][i]+(m-map[i][j])*rate[1][i]; if(numa>numh) continue; add(i,n1+j); } if(xyl()==n2) {flag=1;r=m-1;} else l=m+1; } if(flag) return l; else return -1; } int main() { int i,j; while(~scanf("%d%d",&n1,&n2) && !(n1==0 && n2==0)) { for(i=1;i<=n1;i++) scanf("%I64d%I64d",&init[1][i],&rate[1][i]); for(i=1;i<=n2;i++) scanf("%I64d%I64d",&init[2][i],&rate[2][i]); for(i=1;i<=n1;i++) for(j=1;j<=n2;j++) scanf("%I64d",&map[i][j]); ll ans=bsearch(0,1000000000000LL); if(ans==-1) printf("IMPOSSIBLE\n"); else printf("%I64d\n",ans); } return 0; }