- 1
- #include
- 2
- #include
- 3
- #include
- 4 #define
- MAXN 100010
- 5
- 6 using namespace std;
- 7
- 8 const int
- INF=
- 0x7fffffff;
- 9
- 10 int
- a[
- 1010
- ][
- 1010],fee[MAXN],pre[MAXN];
- 11
- 12 int n,m,src,decc,ans;
- 13
- 14 struct node {
- 15 int to;
- 16 int cost;
- 17 int next;
- 18 int val;
- 19 };
- 20
- node e[MAXN*
- 2];
- 21
- 22 int
- head[MAXN],tot=
- 1;
- 23
- 24 bool vis[MAXN];
- 25
- 26
- queue<
- int
- >
- q;
- 27
- 28
- inline
- void
- read(
- int
- &
- x) {
- 29 int
- f=
- 1
- ;x=
- 0
- ;
- char
- c=
- getchar();
- 30 while
- (c>
- '9'
- ||c<
- '0'
- ) {
- if
- (c==
- '-'
- ) f=-
- 1
- ;c=
- getchar();}
- 31 while
- (c>=
- '0'
- &&c<=
- '9'
- ) {x=(x<<
- 1
- )+(x<<
- 3
- )+c-
- 48
- ;c=
- getchar();}
- 32
- x=x*
- f;
- 33 }
- 34
- 35
- inline
- void
- add(
- int
- x,
- int
- y,
- int
- val,
- int cost) {
- 36
- e[++tot].to=
- y;
- 37
- e[tot].val=
- val;
- 38
- e[tot].cost=
- cost;
- 39
- e[tot].next=
- head[x];
- 40
- head[x]=
- tot;
- 41 }
- 42
- 43
- inline
- void
- add_edge(
- int
- x,
- int
- y,
- int
- val,
- int cost) {
- 44 add(x,y,val,cost);
- 45
- add(y,x,
- 0
- ,-
- cost);
- 46 }
- 47
- 48
- inline
- int min_flow() {
- 49 int
- flow=
- INF;
- 50 for
- (
- int
- i=pre[decc];i;i=pre[e[i^
- 1].to])
- 51
- flow=
- min(flow,e[i].val);
- 52 for
- (
- int
- i=pre[decc];i;i=pre[e[i^
- 1].to])
- 53
- e[i].val-=flow,e[i^
- 1
- ].val+=
- flow;
- 54 return flow;
- 55 }
- 56
- 57
- inline
- bool spfa() {
- 58 for
- (
- int
- i=
- 1
- ;i<=decc;i++) fee[i]=
- INF;
- 59
- fee[src]=
- 0;
- 60
- vis[src]=
- true;
- 61 while
- (!
- q.empty()) q.pop();
- 62 q.push(src);
- 63 while
- (!
- q.empty()) {
- 64 int
- u=
- q.front();
- 65 q.pop();
- 66
- vis[u]=
- false;
- 67 for
- (
- int
- i=head[u];i;i=
- e[i].next) {
- 68 int
- to=
- e[i].to;
- 69 if
- (fee[u]+e[i].cost
- e[i].val) {
- 70
- fee[to]=fee[u]+
- e[i].cost;
- 71
- pre[to]=
- i;
- 72 if
- (!
- vis[to]) {
- 73 q.push(to);
- 74
- vis[to]=
- true;
- 75 }
- 76 }
- 77 }
- 78 }
- 79 return
- fee[decc]!=
- INF;
- 80 }
- 81
- 82
- inline
- void build_graph() {
- 83 for
- (
- int
- i=
- 1
- ;i<=n;i++
- )
- 84 for
- (
- int
- j=
- 1
- ;j<=m;j++
- )
- 85 for
- (
- int
- k=
- 1
- ;k<=n;k++
- )
- 86
- add_edge(i,j*n+k,
- 1
- ,a[i][j]*
- k);
- 87
- src=n*m+n+
- 1
- ;decc=n*m+n+
- 2;
- 88 for
- (
- int
- i=
- 1
- ;i<=n;i++
- )
- 89
- add_edge(src,i,
- 1
- ,
- 0);
- 90 for
- (
- int
- i=n+
- 1
- ;i<=n*m+n;i++
- )
- 91
- add_edge(i,decc,
- 1
- ,
- 0);
- 92 }
- 93
- 94 int main() {
- 95 read(m);read(n);
- 96 for
- (
- int
- i=
- 1
- ;i<=n;i++
- )
- 97 for
- (
- int
- j=
- 1
- ;j<=m;j++
- )
- 98 read(a[i][j]);
- 99 build_graph();
- 100 while
- (spfa()) ans+=min_flow()*
- fee[decc];
- 101
- printf(
- "%.2lf\n"
- ,(
- double
- )ans/
- n);
- 102 return 0;
- 103
- }
来源: http://www.bubuko.com/infodetail-2213231.html